skip to main content
research-article

Bicriteria approximation tradeoff for the node-cost budget problem

Published: 23 March 2009 Publication History

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 + ϵ, O(1/ε log n))-approximation.

References

[1]
Feige, U. 1998.Threshold of ln n for approximating set cover. J. ACM 45, 4, 634--652.
[2]
Garg, N. 2005.Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, New York, 396--402.
[3]
Goemans, M. X., and Williamson, D. P. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 2, 296--317.
[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]
Guha, S., Moss, A., Naor, J., and Schieber, B. 1999.Efficient recovery from power outage. In Proceedings of the 31st ACM Symposium on Theory of Computing. ACM, New York, 574--582.
[6]
Jain, K., and Hajiaghayi, M. T. 2006. The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. 631--640.
[7]
Johnson, D. S., Minkoff, M., and Phillips, S. 2000. The prize collecting steiner tree problem: theory and practice. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 760--769.
[8]
Khuller, S., Moss, A., and Naor, S. 1999. The budgeted maximum coverage problem. Inf. Proc. Lett. 70, 1, 39--45.
[9]
Klein, P. N., and Ravi, R. 1995. A nearly best-possible approximation algorithm for node-weighted steiner trees. J. Algor. 19, 1, 104--115.
[10]
Marathe, M. V., Ravi, R., Sundaram, R., Ravi, S. S., Rosenkrantz, D. J., and Hunt III, H. B. 1998. Bicriteria network design problems. J. Algor. 28, 1, 142--171.
[11]
Moss, A., and Rabani, Y. 2007. Approximation algorithms for constrained node-weighted steiner tree problems. SIAM J. Compu. 37, 2, 460--481.
[12]
Ravi, R., and Goemans, M. X. 1996. The constrained minimum spanning tree problem. In Proceedings of the 5th Scandinavian Workshop on Algorithmic Theory. 66--75.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms
ACM Transactions on Algorithms  Volume 5, Issue 2
March 2009
235 pages
ISSN:1549-6325
EISSN:1549-6333
DOI:10.1145/1497290
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 March 2009
Accepted: 01 October 2008
Revised: 01 May 2007
Received: 01 January 2006
Published in TALG Volume 5, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Approximation algorithms
  2. bicriteria approximation

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 325
    Total Downloads
  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media