Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Approximating Minimum Label s-t Cut via Linear Programming
verfasst von : Linqing Tang, Peng Zhang
Erschienen in: LATIN 2012: Theoretical Informatics
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
We consider the Minimum Label
s
-
t
Cut problem. Given an undirected graph
G
= (
V
,
E
) with a label set
L
, in which each edge has a label from
L
, and a source
s
∈
V
together with a sink
t
∈
V
, the goal of the Minimum Label
s
-
t
Cut problem is to pick a subset of labels of minimized cardinality, such that the removal of all edges with these labels from
G
disconnects
s
and
t
. We present a min {
O
((
m
/
OPT
)
1/2
),
O
(
n
2/3
/
OPT
1/3
) }-approximation algorithm for the Minimum Label
s
-
t
Cut problem using linear programming technique, where
n
= |
V
|,
m
= |
E
|, and
OPT
is the optimal value of the input instance. This result improves the previously best known approximation ratio
O
(
m
1/2
) for this problem (Zhang et al., JOCO 21(2), 192–208 (2011)), and gives the first approximation ratio for this problem in terms of
n
. Moreover, we show that our linear program relaxation for the Minimum Label
s
-
t
Cut problem, even in a stronger form, has integrality gap Ω((
m
/
OPT
)
1/2 −
ε
).