Abstract
In this paper we design an iterative rounding approach for the classic prize-collecting Steiner forest problem and more generally the prize-collecting survivable Steiner network design problem. We show as an structural result that in each iteration of our algorithm there is an LP variable in a basic feasible solution which is at least one-third-integral resulting a 3-approximation algorithm for this problem. In addition, we show this factor 3 in our structural result is indeed tight for prize-collecting Steiner forest and thus prize-collecting survivable Steiner network design. This especially answers negatively the previous belief that one might be able to obtain an approximation factor better than 3 for these problems using a natural iterative rounding approach. Our structural result is extending the celebrated iterative rounding approach of Jain [13] by using several new ideas some from more complicated linear algebra. The approach of this paper can be also applied to get a constant factor (bicriteria-)approximation algorithm for degree constrained prize-collecting network design problems.
We emphasize that though in theory we can prove existence of only an LP variable of at least one-third-integral, in practice very often in each iteration there exists a variable of integral or almost integral which results in a much better approximation factor than provable factor 3 in this paper (see patent application [11]). This is indeed the advantage of our algorithm in this paper over previous approximation algorithms for prize-collecting Steiner forest with the same or slightly better provable approximation factors.
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
Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: FOCS 1997, p. 542 (1997)
Balas, E.: The prize collecting traveling salesman problem. Networks 19, 621–636 (1989)
Bansal, N., Khandekar, R., Nagarajan, V.: Additive guarantees for degree bounded directed network design. In: STOC 2008, pp. 769–778 (2008)
Becchetti, L., Konemann, J., Leonardi, S., Pal, M.: Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy. In: SODA 2005, pp. 375–384 (2005)
Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.: A note on the prize collecting traveling salesman problem. Math. Prog. 59, 413–420 (1993)
Chudak, F.A., Roughgarden, T., Williamson, D.P.: Approximate k-MSTs and k-Steiner trees via the primal-dual method and lagrangean relaxation. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, pp. 60–70. Springer, Heidelberg (2001)
Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296–317 (1995)
Gupta, A., Könemann, J., Leonardi, S., Ravi, R., Schäfer, G.: An efficient cost-sharing mechanism for the prize-collecting steiner forest problem. In: SODA 2007, pp. 1153–1162 (2007)
Gupta, A., Kumar, A., Pal, M., Roughgarden, T.: Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem. In: FOCS 2003, p. 606 (2003)
Gutner, S.: Elementary approximation algorithms for prize collecting Steiner tree problems. Inf. Process. Lett. 107, 39–44 (2008)
M. Hajiaghayi, Designing minimum total cost networks using iterative rounding approximation methods. Pending patent with USPTO of application number 12/315,657 (July 2008)
Hajiaghayi, M.T., Jain, K.: The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In: SODA 2006, pp. 631–640 (2006)
Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 39–60 (2001)
Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48, 274–296 (2001)
Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting Steiner tree problem: theory and practice. In: SODA 2000, pp. 760–769 (2000)
Karger, D.R., Minkoff, M.: Building steiner trees with incomplete global knowledge. In: FOCS 2001, p. 613 (2001)
Kumar, A., Gupta, A., Roughgarden, T.: A constant-factor approximation algorithm for the multicommodity. In: FOCS 2002, p. 333 (2002)
Lau, L.C., Naor, J.S., Salavatipour, M.R., Singh, M.: Survivable network design with degree or order constraints. In: STOC 2007, pp. 651–660 (2007)
Lau, L.C., Singh, M.: Additive approximation for bounded degree survivable network design. In: STOC 2008, pp. 759–768 (2008)
Salman, F.S., Cheriyan, J., Ravi, R., Subramanian, S.: Approximating the single-sink link-installation problem in network design. SIAM J. Optim. 11, 595–610 (2000)
Sharma, Y., Swamy, C., Williamson, D.P.: Approximation algorithms for prize collecting forest problems with submodular penalty functions. In: SODA 2007, pp. 1275–1284 (2007)
Konemann, J., Grandoni, F., Rothvoss, T., Qian, J., Schaefer, G., Swamy, C., Williamson, D.P.: An iterated rounding 3-approximation algorithm for prize-collecting Steiner forest (2009) (unpublished manuscript)
Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: STOC 2007, pp. 661–670 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hajiaghayi, M., Nasri, A.A. (2010). Prize-Collecting Steiner Networks via Iterative Rounding. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_45
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)