Könemann, Jochen ;
Olver, Neil ;
Pashkovich, Kanstantsin ;
Ravi, R. ;
Swamy, Chaitanya ;
Vygen, Jens
On the Integrality Gap of the PrizeCollecting Steiner Forest LP
Abstract
In the prizecollecting 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 wellstudied) linearprogramming (LP) relaxation for PCSF (PCSFLP) 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 Lagrangianmultiplierpreserving (LMP) algorithm with approximation guarantee better than 4. Our results thus show a separation between the integrality gaps of the LPrelaxations for prizecollecting and nonprizecollecting (i.e., standard) Steiner forest, as well as the approximation ratios achievable relative to the optimal LP solution by LMP and nonLMPapproximation algorithms for PCSF. For the special case of prizecollecting 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.
BibTeX  Entry
@InProceedings{knemann_et_al:LIPIcs:2017:7566,
author = {Jochen K{\"o}nemann and Neil Olver and Kanstantsin Pashkovich and R. Ravi and Chaitanya Swamy and Jens Vygen},
title = {{On the Integrality Gap of the PrizeCollecting Steiner Forest LP}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {17:117:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770446},
ISSN = {18688969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7566},
URN = {urn:nbn:de:0030drops75665},
doi = {10.4230/LIPIcs.APPROXRANDOM.2017.17},
annote = {Keywords: Integrality gap, Steiner tree, Steiner forest, prizecollecting, Lagrangianmultiplier preserving}
}
2017
Keywords: 

Integrality gap, Steiner tree, Steiner forest, prizecollecting, Lagrangianmultiplier preserving 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Issue date: 

2017 
Date of publication: 

2017 