𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation Algorithms for the Unsplittable Flow Problem

✍ Scribed by Amit Chakrabarti; Chandra Chekuri; Anupam Gupta; Amit Kumar

Publisher
Springer
Year
2006
Tongue
English
Weight
270 KB
Volume
47
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A note on the greedy algorithm for the u
A note on the greedy algorithm for the unsplittable flow problem
✍ Petr Kolman πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 161 KB

In a recent paper Chekuri and Khanna improved the analysis of the greedy algorithm for the edge disjoint paths problem and proved the same bounds also for the related uniform capacity unsplittable flow problem. Here we show that their ideas can be used to get the same approximation ratio even for th

Combinatorial Approximation Algorithms f
Combinatorial Approximation Algorithms for Generalized Flow Problems
✍ Jeffrey D Oldham πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 226 KB

Generalized network flow problems generalize normal network flow problems by specifying a flow multiplier Β΅ v w for each arc v w . For every unit of flow entering the arc, Β΅ v w units of flow exit. We present a strongly polynomial algorithm for a single-source generalized shortest paths problem, usi