17 marca 2015 10:15
[Seminarium ZOK]. Mateusz Lewandowski: Constant Approximation Algorithm for Node-Weighted Prize-Collecting Steiner Forest on Planar Graphs
Wtorek, 10:15-12:00, sala 310.
Abstract. In this talk I will present some variation of a classical Steiner forest problem. The input node-weighted graph is planar. The goal is to connect some pairs of vertices by buying nodes. We can also decide not to connect the demand but it involves paying a penalty. We want to minimize the cost of bought nodes and penalties. We will mainly discuss a 4 approximation algorithm for this problem. We will see a nice technique of handling prize-collecting setting using Farkas Lemma introduced by Hajiaghayi and Jain. The algorithm is some modification of a generic primal-dual approximation algorithm given by Goemans and Williamson. It was developed as part of the semestral project during my exchange at EPFL (supervisor: C. Moldenhauer)