|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
On the Integrality Gap of the Prize-Collecting Steiner Forest LP | | Jochen Könemann
; Neil Olver
; Kanstantsin Pashkovich
; R. Ravi
; Chaitanya Swamy
; Jens Vygen
; | | Date: |
20 Jun 2017 | | Abstract: | In the prize-collecting Steiner forest (PCSF) problem, we are given an
undirected graph $G=(V,E)$, edge costs ${c_egeq 0}_{ein E}$, terminal pairs
${(s_i,t_i)}_{i=1}^k$, and penalties ${pi_i}_{i=1}^k$ for each terminal
pair; the goal is to find a forest $F$ to minimize $c(F)+sum_{i:
(s_i,t_i) ext{ not connected in }F}pi_i$. The Steiner forest problem can be
viewed as the special case where $pi_i=infty$ for all $i$. It was widely
believed that the integrality gap of the natural (and well-studied)
linear-programming (LP) relaxation for PCSF is at most 2. We dispel this belief
by showing that the integrality gap of this LP is at least $9/4$. This holds
even for planar graphs. 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. | | Source: | arXiv, 1706.6565 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER