Oct. 20, 2015, 10:15 a.m.
[COG seminar]. Mateusz Lewandowski: Approximation algorithms for the node-weighted prize-collecting Steiner tree problem (NWPCST) on planar graphs
Tuesday 10:15-12:00, room 310.
Abstract. In the talk I will present extended results from my Master Thesis. In particular we will see the new primal-dual 3-approximation algorithm for the node-weighted prize-collecting Steiner tree problem (NWPCST) on planar graphs. We will prove that it is also Lagrangian-preserving. Our algorithm combined with a randomized rounding technique gives us the (2.87 + eps)-approximation algorithm which is the best result for this problem.