The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
Mohammad Taghi Hajiaghayi, Kamal Kishore Jain · 2006
In this paper we study the prize-collecting version of the Generalized Steiner Tree problem. To the best of our knowledge, there is no general combinatorial technique in approximation algorithms developed to study the prize-collecting versions of various problems. These problems are studied on a case by case basis by Bienstock et al. [5] by applying an LP-rounding technique which is not a combinatorial approach. The main contribution of this paper is to introduce a general combinatorial approach towards solving these problems through novel primal-dual schema (without any need to solve an LP). We fuse the primal-dual schema with Farkas lemma to obtain a combinatorial 3-approximation algorithm for the Prize-Collecting Generalized Steiner Tree problem. Our work also inspires a combinatorial algorithm [12] for solving a special case of Kelly’s problem [21] of pricing edges. We also consider the k-forest problem, a generalization of k-MST and k-Steiner tree, and we show that in spite of these problems for which there are constant factor approximation algorithms, the k-forest problem is much harder to approximate. In particular, obtaining an approximation factor better than O(n 1/6−ε) for kforest requires substantially new ideas including improving the approximation factor O(n 1/3−ε) for the notorious densest k-subgraph problem. We note that k-forest and prize-collecting version of Generalized Steiner Tree are closely related to each other, since the latter is the Lagrangian relaxation of the former.