2026-07-20T14:47:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7566 2024-03-06T10:40:38Z ddc:004 open_access

On the Integrality Gap of the Prize-Collecting Steiner Forest LP Könemann, Jochen Olver, Neil Pashkovich, Kanstantsin Ravi, R. Swamy, Chaitanya Vygen, Jens Integrality gap Steiner tree Steiner forest prize-collecting Lagrangianmultiplier- preserving 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jochen Könemann and Neil Olver and Kanstantsin Pashkovich and R. Ravi and Chaitanya Swamy and Jens Vygen 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.17 urn:nbn:de:0030-drops-75665 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.17 eng https://creativecommons.org/licenses/by/3.0/legalcode