๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Combinatorial Algorithms for the Unsplittable Flow Problem

โœ Scribed by Yossi Azar; Oded Regev

Publisher
Springer
Year
2005
Tongue
English
Weight
311 KB
Volume
44
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

Combinatorial algorithms for inverse net
Combinatorial algorithms for inverse network flow problems
โœ Ravindra K. Ahuja; James B. Orlin ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 122 KB

An inverse optimization problem is defined as follows: Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost vector, and x 0 สฆ S. We want to perturb the cost vector c to d so that x 0 is an optimal solution of P with respect to the cost vector d, and wสˆd