Unsplittable flow in paths and trees and column-restricted packing integer programs

Chandra Chekuri, Alina Ene, Nitish Korula

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 R1, ..., R k, where each Ri consists of a source-destination pair (si, ti), a demand di 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(logn) approximation for UFP on trees when all weights are identical; this yields an O(log2 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(log2 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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings
Pages42-55
Number of pages14
DOIs
StatePublished - Nov 6 2009
Event12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 - Berkeley, CA, United States
Duration: Aug 21 2009Aug 23 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5687 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
CountryUnited States
CityBerkeley, CA
Period8/21/098/23/09

Fingerprint

Integer Program
Packing
Path
Approximation
LP Relaxation
Integrality
Graph in graph theory
Subset

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Chekuri, C., Ene, A., & Korula, N. (2009). Unsplittable flow in paths and trees and column-restricted packing integer programs. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings (pp. 42-55). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5687 LNCS). https://doi.org/10.1007/978-3-642-03685-9_4

Unsplittable flow in paths and trees and column-restricted packing integer programs. / Chekuri, Chandra; Ene, Alina; Korula, Nitish.

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. 2009. p. 42-55 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5687 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Chekuri, C, Ene, A & Korula, N 2009, Unsplittable flow in paths and trees and column-restricted packing integer programs. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5687 LNCS, pp. 42-55, 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009, Berkeley, CA, United States, 8/21/09. https://doi.org/10.1007/978-3-642-03685-9_4
Chekuri C, Ene A, Korula N. Unsplittable flow in paths and trees and column-restricted packing integer programs. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. 2009. p. 42-55. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-03685-9_4
Chekuri, Chandra ; Ene, Alina ; Korula, Nitish. / Unsplittable flow in paths and trees and column-restricted packing integer programs. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. 2009. pp. 42-55 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{737aebe8cdfc4c85b197d99cf0d7104d,
title = "Unsplittable flow in paths and trees and column-restricted packing integer programs",
abstract = "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 R1, ..., R k, where each Ri consists of a source-destination pair (si, ti), a demand di 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(logn) approximation for UFP on trees when all weights are identical; this yields an O(log2 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(log2 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.",
author = "Chandra Chekuri and Alina Ene and Nitish Korula",
year = "2009",
month = "11",
day = "6",
doi = "10.1007/978-3-642-03685-9_4",
language = "English (US)",
isbn = "3642036848",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "42--55",
booktitle = "Approximation, Randomization, and Combinatorial Optimization",

}

TY - GEN

T1 - Unsplittable flow in paths and trees and column-restricted packing integer programs

AU - Chekuri, Chandra

AU - Ene, Alina

AU - Korula, Nitish

PY - 2009/11/6

Y1 - 2009/11/6

N2 - 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 R1, ..., R k, where each Ri consists of a source-destination pair (si, ti), a demand di 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(logn) approximation for UFP on trees when all weights are identical; this yields an O(log2 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(log2 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.

AB - 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 R1, ..., R k, where each Ri consists of a source-destination pair (si, ti), a demand di 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(logn) approximation for UFP on trees when all weights are identical; this yields an O(log2 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(log2 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.

UR - http://www.scopus.com/inward/record.url?scp=70350614880&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350614880&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03685-9_4

DO - 10.1007/978-3-642-03685-9_4

M3 - Conference contribution

AN - SCOPUS:70350614880

SN - 3642036848

SN - 9783642036842

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 42

EP - 55

BT - Approximation, Randomization, and Combinatorial Optimization

ER -