2009 | OriginalPaper | Buchkapitel
Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
verfasst von : Chandra Chekuri, Alina Ene, Nitish Korula
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
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 unsplittable flow problem (UFP) and the closely related column-restricted packing integer programs (CPIPs). In UFP we are given an edge-capacitated graph
G
= (
V
,
E
) and
k
request pairs
R
1
, …,
R
k
, where each
R
i
consists of a source-destination pair (
s
i
,
t
i
), a demand
d
i
and a weight
w
i
. The goal is to find a maximum weight subset of requests that can be routed unsplittably in
G
. Most previous work on UFP has focused on the
no-bottleneck
case in which the maximum demand of the requests is at most the smallest edge capacity. Inspired by the recent work of Bansal
et
al
. [3] on UFP on a path without the above assumption, we consider UFP on paths as well as trees. We give a simple
O
(log
n
) approximation for UFP on trees when all weights are identical; this yields an
O
(log
2
n
) approximation for the weighted case. These are the first non-trivial approximations for UFP on trees. We develop an LP relaxation for UFP on paths that has an integrality gap of
O
(log
2
n
); previously there was no relaxation with
o
(
n
) gap. We also consider UFP in general graphs and CPIPs without the no-bottleneck assumption and obtain new and useful results.