Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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.

REFERENCES

• 1: Sanjeev Arora , George Karakostas, A 2 + &egr; approximation algorithm for the k-MST problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.754-759, January 09-11, 2000, San Francisco, California, United States
• 2: Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 3: Baruch Awerbuch , Yossi Azar , Avrim Blum , Santosh Vempala, Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.277-283, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225139]
• 4: Avrim Blum , R. Ravi , Santosh Vempala, A constant-factor approximation algorithm for the k MST problem (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.442-448, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237992]
• 5: Robert Carr , Santosh Vempala, Randomized metarounding (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.58-62, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335312]
• 6: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
• 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.
• 8: R. Diestel. Graph Theory, 2nd Edition. Graduate Texts in Mathematics, Volume 173, Springer-Verlag, 2000.
• 9: N. Garg, A 3-approximation for the minimum tree spanning k vertices, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.302, October 14-16, 1996
• 10: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 11: M. Gr.otschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, second corrected edition. Springer-Verlag, 1993.
• 12: Sudipto Guha , Anna Moss , Joseph (Seffi) Naor , Baruch Schieber, Efficient recovery from power outage (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.574-582, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301406]
• 13: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 14: Kamal Jain , Vijay V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.2, October 17-18, 1999
• 15: David S. Johnson , Maria Minkoff , Steven Phillips, The prize collecting Steiner tree problem: theory and practice, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.760-769, January 09-11, 2000, San Francisco, California, United States
• 16: Samir Khuller , Anna Moss , Joseph (Seffi) Naor, The budgeted maximum coverage problem, Information Processing Letters, v.70 n.1, p.39-45, April 01, 1999 [doi>10.1016/S0020-0190(99)00031-9]
• 17: Philip Klein , R. Ravi, A nearly best-possible approximation algorithm for node-weighted Steiner trees, Journal of Algorithms, v.19 n.1, p.104-115, July 1995 [doi>10.1006/jagm.1995.1029]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Performance, Theory, Verification