20 października 2015 10:15
[Seminarium ZOK]. Mateusz Lewandowski: Approximation algorithms for the node-weighted prize-collecting Steiner tree problem (NWPCST) on planar graphs
Wtorek, 10:15-12:00, sala 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.