Document Open Access Logo

On the Integrality Gap of the Prize-Collecting Steiner Forest LP

Authors Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy, Jens Vygen

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2017.17.pdf
  • Filesize: 0.54 MB
  • 13 pages

Document Identifiers

Subject Classification

Keywords
  • Integrality gap
  • Steiner tree
  • Steiner forest
  • prize-collecting
  • Lagrangianmultiplier- preserving

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph G=(V,E), nonnegative edge costs {c_e} for e in E, terminal pairs {(s_i,t_i)} for i=1,...,k, and penalties {pi_i} for i=1,...,k for each terminal pair; the goal is to find a forest F to minimize c(F) + sum{ pi_i: (s_i,t_i) is not connected in F }. The Steiner forest problem can be viewed as the special case where pi_i are infinite for all i. It was widely believed that the integrality gap of the natural (and well-studied) linear-programming (LP) relaxation for PCSF (PCSF-LP) is at most 2. We dispel this belief by showing that the integrality gap of this LP is at least 9/4 even if the input instance is planar. We also show that using this LP, one cannot devise a Lagrangian-multiplier-preserving (LMP) algorithm with approximation guarantee better than 4. Our results thus show a separation between the integrality gaps of the LP-relaxations for prize-collecting and non-prize-collecting (i.e., standard) Steiner forest, as well as the approximation ratios achievable relative to the optimal LP solution by LMP- and non-LMP-approximation algorithms for PCSF. For the special case of prize-collecting Steiner tree (PCST), we prove that the natural LP relaxation admits basic feasible solutions with all coordinates of value at most 1/3 and all edge variables positive. Thus, we rule out the possibility of approximating PCST with guarantee better than 3 using a direct iterative rounding method.

Cite As Get BibTex

Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy, and Jens Vygen. On the Integrality Gap of the Prize-Collecting Steiner Forest LP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.17

Author Details

Jochen Könemann
Neil Olver
Kanstantsin Pashkovich
R. Ravi
Chaitanya Swamy
Jens Vygen

References

  1. A. Agrawal, P. Klein, and R. Ravi. When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 24(3):440-456, 1995. Google Scholar
  2. A. Archer, M. Bateni, M. Hajiaghayi, and H. Karloff. Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM Journal on Computing, 40(2):309-332, 2011. Google Scholar
  3. D. Bienstock, M. X. Goemans, D. Simchi-Levi, and D. Williamson. A note on the prize collecting traveling salesman problem. Mathematical Programming, 59(1):413-420, 1993. Google Scholar
  4. A. Blum, R. Ravi, and S. Vempala. A constant-factor approximation algorithm for the k-MST problem. Journal of Computer and System Sciences, 58(1):101-108, 1999. Google Scholar
  5. J. Byrka, F. Grandoni, T. Rothvoss, and L. Sanità. Steiner tree approximation via iterative randomized rounding. Journal of the ACM, 60(1):6, 2013. Google Scholar
  6. R. D. Carr and S. Vempala. On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems. Mathematical Programming A, 100:569-587, 2004. Google Scholar
  7. M. Chlebík and J. Chlebíková. The Steiner tree problem on graphs: Inapproximability results. Theoretical Computer Science, 406(3):207-214, 2008. URL: http://dx.doi.org/10.1016/j.tcs.2008.06.046.
  8. F. A. Chudak, T. Roughgarden, and D. P. Williamson. Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Mathematical Programming, 100(2):411-421, 2004. Google Scholar
  9. N. Garg. Saving an epsilon: a 2-approximation algorithm for the k-MST problem in graphs. In Proceedings of the 37th ACM Symposium on Theory of Computing, pages 396-402, 2005. Google Scholar
  10. K. Georgiou and C. Swamy. Black-box reductions for cost-sharing mechanism design. Games and Economic Behavior, 2013. URL: http://dx.doi.org/10.1016/j.geb.2013.08.012.
  11. M. X. Goemans, N. Olver, T. Rothvoß, and R. Zenklusen. Matroids and integrality gaps for hypergraphic Steiner tree relaxations. In Proceedings of the 44th ACM Symposium on Theory of Computing, pages 1161-1176, 2012. Google Scholar
  12. M. X. Goemans and D. P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296-317, 1995. Google Scholar
  13. M. Hajiaghayi and K. Jain. The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 631-640, 2006. Google Scholar
  14. M. Hajiaghayi and A. Nasri. Prize-collecting Steiner networks via iterative rounding. In Theoretical Informatics: LATIN 2010, pages 515-526. Springer, 2010. Google Scholar
  15. K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39-60, 2001. URL: http://dx.doi.org/10.1007/s004930170004.
  16. K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM, 48(2):274-296, 2001. Google Scholar
  17. R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85-103. Springer, 1972. Google Scholar
  18. J. Könemann, O. Parekh, and D. Segev. A unified approach to approximating partial covering problems. Algorithmica, 59(4):489-509, 2011. Google Scholar
  19. E. Steinitz. Polyeder und Raumeinteilungen. In Enzyclopädie der Mathematischen Wissenschaften, vol. 3, Geometrie, erster Teil, zweite Hälfte, pages 1-139. Teubner, 1922. Google Scholar
  20. D. P. Williamson and D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact