✦ LIBER ✦

A note on the greedy algorithm for the unsplittable flow problem

✍ Scribed by Petr Kolman

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 161 KB
Volume: 88
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(03)00351-x

No coin nor oath required. For personal study only.

✦ Synopsis

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 the more general Unsplittable Flow Problem with nonuniform edge capacities.

📜 SIMILAR VOLUMES

Combinatorial Algorithms for the Unsplit

Combinatorial Algorithms for the Unsplittable Flow Problem

✍ Yossi Azar; Oded Regev 📂 Article 📅 2005 🏛 Springer 🌐 English ⚖ 311 KB

Approximation Algorithms for the Unsplit

Approximation Algorithms for the Unsplittable Flow Problem

✍ Amit Chakrabarti; Chandra Chekuri; Anupam Gupta; Amit Kumar 📂 Article 📅 2006 🏛 Springer 🌐 English ⚖ 270 KB

On the Single-Source Unsplittable Flow P

On the Single-Source Unsplittable Flow Problem

✍ Yefim Dinitz; Naveen Garg; Michel X. Goemans 📂 Article 📅 1999 🏛 Springer-Verlag 🌐 English ⚖ 323 KB

Note: On the greedy algorithm for optima

Note: On the greedy algorithm for optimal assembly

✍ Laurence A. Baxter; Farid Harche 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 245 KB 👁 2 views

Greedy algorithm for the general multidi

Greedy algorithm for the general multidimensional knapsack problem

✍ Yalçın Akçay; Haijun Li; Susan H. Xu 📂 Article 📅 2006 🏛 Springer US 🌐 English ⚖ 328 KB

A Greedy On-Line Algorithm for thek-Trac

A Greedy On-Line Algorithm for thek-Track Assignment Problem

✍ U Faigle; W Kern; W.M Nawijn 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 107 KB

Given a collection I I of n jobs that are represented by intervals, we seek a maximal feasible assignment of the jobs to k machines such that not more than Ž . c M intervals overlap pairwise on any machine M and that a job is only assigned to a machine if it fits into one of several prescribed time