direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 685-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Approximating the single source unsplittable min-cost flow problem
Mathematical Programming B, to appear. An extended abstract appeared in Proceedings of 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS'00), pp. 136-145.
primary: 90C27 Combinatorial optimization
secondary: 90B10 Network models, deterministic
90C35 Programming involving graphs or networks
05C38 Paths and cycles
05C85 Graph algorithms
90C59 Approximation methods and heuristics
Approximation algorithms, graph algorithms, network flow, routing
In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path and the total cost must not exceed a given budget. This problem has been introduced by Kleinberg and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing and virtual-circuit routing.
Kolliopoulos & Stein and Dinitz, Garg & Goemans developed algorithms improving the first approximation results of Kleinberg for the problem to minimize the violation of edge capacities and for other variants. However, none of the developed techniques is capable of providing solutions without also violating the cost constraint. We give the first approximation results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally, we provide results on the hardness of approximation for several variants of the problem.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe