ABSTRACT
We consider a class of optimization problems, where the input is an undirected graph with two weight functions defined for each node, namely the node's profit and its cost. The goal is to find a connected set of nodes of low cost and high profit. We present approximation algorithms for three natural optimization criteria that arise in this context, all of which are NP-hard. The budget problem asks for maximizing the profit of the set subject to a budget constraint on its cost. The quota problem requires minimizing the cost of the set subject to a quota constraint on its profit. Finally, the prize collecting problem calls for minimizing the cost of the set plus the profit (here interpreted as a penalty) of the complement set. For all three problems, our algorithms give an approximation guarantee of O(\log n), where n is the number of nodes. To the best of our knowledge, these are the first approximation results for the quota problem and for the prize collecting problem, both of which are at least as hard to approximate as set cover. For the budget problem, our results improve on a previous O(\log^2 n) result of Guha, Moss, Naor, and Schieber. Our methods involve new theorems relating tree packings to (node) cut conditions. We also show similar theorems (with better bounds) using edge cut conditions. These imply bounds for the analogous budget and quota problems with edge costs which are comparable to known (constant factor) bounds.
- 1.S. Arora and G. Karakostas. A 2 + x approximation algorithm for the k-MST problem. In Proc. of the 11th SODA, January 2000. Google ScholarDigital Library
- 2.S. Arora and C. Lund. Hardness of approximations. Chapter 10 in {13}. Google ScholarDigital Library
- 3.B. Awerbuch, Y. Azar, A. Blum, and S. Vempala. Improved approximations for minimum-weight k-trees and prize-collecting salesmen. In Proc. of the 27th STOC, May 1995. Google ScholarDigital Library
- 4.A. Blum, R. Ravi, and S. Vempala. A constant factor approximation for the k-MST problem. In Proc. of the 28th STOC, 1996. Google ScholarDigital Library
- 5.R. Carr and S. Vempala. Randomized metarounding. In Proc. of the 32nd STOC, May 2000. Google ScholarDigital Library
- 6.M. Charikar and S. Guha. Improved combinatorial algorithms for the facility location and k-median problems. In Proc. of the 40th FOCS, October 1999. Google ScholarDigital Library
- 7.F. Chudak, T. Roughgarden, and D.P. Williamson. Some notes on Garg's approximation algorithms for the k-MST problem. In Proc. of the 12th SODA.Google Scholar
- 8.R. Diestel. Graph Theory, 2nd Edition. Graduate Texts in Mathematics, Volume 173, Springer-Verlag, 2000.Google Scholar
- 9.N. Garg. A 3-approximation for the minimum tree spanning k vertices. In Proc. of the 37th FOCS, 1996. Google ScholarDigital Library
- 10.M.X. Goemans and D.P. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput., 24(2):296{317, 1995. Google ScholarDigital Library
- 11.M. Gr.otschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, second corrected edition. Springer-Verlag, 1993.Google Scholar
- 12.S. Guha, A. Moss, J. Naor, and B. Schieber. Efficient recovery from power outage. In Proc. of the 13th STOC, May 1999. Google ScholarDigital Library
- 13.D.S. Hochbaum, editor. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997. Google ScholarDigital Library
- 14.K. Jain and V.V. Vazirani. Primal-dual approximation algorithms for metric facility location and k-median problems. In Proc. of the 40th FOCS, October 1999. Google ScholarDigital Library
- 15.D.S. Johnson, M. Minkoff, and S. Phillips. The prize collecting Steiner tree problem: theory and practice. In Proc. of the 11th SODA, January 2000. Google ScholarDigital Library
- 16.S. Khuller, A. Moss, and S. Naor. The budgeted maximum coverage problem. Information Processing Letters, 70(1):39{45, 1998. Google ScholarDigital Library
- 17.P. Klein and R. Ravi. A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. of Algorithms, 19:104{115, 1995. Google ScholarDigital Library
Index Terms
- Approximation algorithms for constrained for constrained node weighted steiner tree problems
Recommendations
Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
We consider a class of optimization problems where the input is an undirected graph with two weight functions defined for each node, namely the node's profit and its cost. The goal is to find a connected set of nodes of low cost and high profit. We ...
Improved approximation algorithms for (budgeted) node-weighted steiner problems
ICALP'13: Proceedings of the 40th international conference on Automata, Languages, and Programming - Volume Part IMoss and Rabani [13] study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an O(logn)-approximation algorithm for the prize-collecting node-...
Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems
Moss and Rabani study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an $O(\log n)$-approximation algorithm for the node-weighted prize-collecting ...
Comments