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

ABSTRACT

We consider an optimization problem consisting of an undirected graph, with cost and profit functions defined on all vertices. The goal is to find a connected subset of vertices with maximum total profit, whose total cost does not exceed a given budget. The best result known prior to this work guaranteed a (2, O(log n)) bicriteria approximation, that is, the solution's profit is at least a fraction of 1/O(log n) of an optimum solution respecting the budget, while its cost is at most twice the given budget. We improve these results and present a bicriteria tradeoff that, given any ϵ ∈ (0,1], guarantees a (1 + &epsis;, O(1/ϵ log n))-approximation.

REFERENCES

• 1: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 2: Naveen Garg, Saving an epsilon: a 2-approximation for the k-MST problem in graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060650]
• 3: 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]
• 4: Grötschel, M., Lóvász, L., and Schrijver, A. 1993.Geometric Algorithms and Combinatorial Optimization, Second corrected ed. Springer-Verlag, Berlin, Germany.
• 5: 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]
• 6: Mohammad Taghi Hajiaghayi , Kamal Jain, The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.631-640, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109626]
• 7: 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
• 8: 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]
• 9: 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]
• 10: Madhav V. Marathe , R. Ravi , Ravi Sundaram , S. S. Ravi , Daniel J. Rosenkrantz , Harry B. Hunt, III, Bicriteria network design problems, Journal of Algorithms, v.28 n.1, p.142-171, July 1, 1998 [doi>10.1006/jagm.1998.0930]
• 11: A. Moss , Y. Rabani, Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems, SIAM Journal on Computing, v.37 n.2, p.460-481, May 2007 [doi>10.1137/S0097539702420474]
• 12: R. Ravi , Michel X. Goemans, The Constrained Minimum Spanning Tree Problem (Extended Abstract), Proceedings of the 5th Scandinavian Workshop on Algorithm Theory, p.66-75, July 03-05, 1996

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Approximation algorithms, bicriteria approximation