March 17, 2015, 10:15 a.m.
[COG seminar]. Mateusz Lewandowski: Constant Approximation Algorithm for Node-Weighted Prize-Collecting Steiner Forest on Planar Graphs
Tuesday 10:15-12:00, room 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)