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
Thumbnail PDF

File

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

Document Identifiers

Author Details

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

Cite AsGet 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

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.
Keywords
  • Integrality gap
  • Steiner tree
  • Steiner forest
  • prize-collecting
  • Lagrangianmultiplier- preserving

Metrics

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

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