### 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 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(logn) 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.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization |

Subtitle of host publication | Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings |

Pages | 42-55 |

Number of pages | 14 |

DOIs | |

State | Published - Nov 6 2009 |

Event | 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 Duration: Aug 21 2009 → Aug 23 2009 |

### Publication series

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

Volume | 5687 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 |
---|---|

Country | United States |

City | Berkeley, CA |

Period | 8/21/09 → 8/23/09 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*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

}

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 -