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(logn)) bicriteria approximation, i.e. the solution’s profit is at least a fraction of \(\frac{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+\varepsilon,O(\frac{1}{\varepsilon}\log n))\)-approximation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Marathe, M., Ravi, R., Sundaram, R., Ravi, S., Rosenkrantz, D. (III), H.H.: Bicriteria network design problems. Journal of Algorithms 28(1), 142–171 (1998)
Moss, A., Rabani, Y.: Approximation algorithms for constrained node weighted steiner tree problems. SIAM Journal on Computing 37(2), 460–481 (2007)
Guha, S., Moss, A., Naor, J., Schieber, B.: Efficient recovery from power outage. In: Proceedings of the 31st ACM Symposium on Theory of Computing, pp. 574–582 (1999)
Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted steiner trees. Journal of Algorithms 19(1), 104–114 (1995)
Feige, U.: Threshold of ln n for approximating set cover. Journal of the ACM 45(4), 634–652 (1998)
Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM Journal on Computing 24(2), 296–317 (1995)
Johnson, D., Minkoff, M., Phillips, S.: The prize collecting steiner tree problem: theory and practice. In: Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms, pp. 760–769 (2000)
Jain, K., Hajiaghayi, M.: 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, pp. 631–640 (2006)
Garg, N.: 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, pp. 396–402 (2005)
Ravi, R., Goemans, M.: The constrained minimum spanning tree problem. In: Proceedings of the 5th Scandinavian Workshop on Algorithmic Theory, pp. 66–75 (1996)
Khuller, S., Moss, A., Naor, S.: The budgeted maximum coverage problem. Information Processing Letters 70(1), 39–45 (1999)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, 2nd edn. Springer, Heidelberg (1993)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rabani, Y., Scalosub, G. (2008). Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem . In: Gudmundsson, J. (eds) Algorithm Theory – SWAT 2008. SWAT 2008. Lecture Notes in Computer Science, vol 5124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69903-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-69903-3_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69900-2
Online ISBN: 978-3-540-69903-3
eBook Packages: Computer ScienceComputer Science (R0)