2010 | OriginalPaper | Buchkapitel
Prize-Collecting Steiner Network Problems
verfasst von : MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the
Steiner Network
problem we are given a graph
G
with edge-costs and connectivity requirements
r
uv
between node pairs
u
,
v
. The goal is to find a minimum-cost subgraph
H
of
G
that contains
r
uv
edge-disjoint paths for all
u
,
v
∈
V
. In
Prize-Collecting Steiner Network
problems we do not need to satisfy all requirements, but are given a
penalty function
for violating the connectivity requirements, and the goal is to find a subgraph
H
that minimizes the cost plus the penalty. The case when
r
uv
∈ {0,1} is the classic
Prize-Collecting Steiner Forest
problem.
In this paper we present a novel linear programming relaxation for the
Prize-Collecting Steiner Network
problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone non-decreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed in [SSW07]. We further generalize our results for element-connectivity and node-connectivity.