Approximating the single source unsplittable min-cost flow problem |
| |
Authors: | Martin Skutella |
| |
Institution: | Technische Universit?t Berlin, Fakult?t II – Mathematik und Naturwissenschaften, MA 6–1, Strasse des 17. Juni 136, D–10623 Berlin, Germany, e-mail: skutella@math.tu-berlin.de, DE
|
| |
Abstract: | 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 so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed
a given budget. This problem has been introduced by Kleinberg 7] and generalizes several NP-complete problems from various
areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing.
Kolliopoulos and Stein 9] and Dinitz, Garg, and Goemans 4] developed algorithms improving the first approximation results
of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques
do not seem to be 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.
Received: August 23, 2000 / Accepted: April 20, 2001?Published online October 2, 2001 |
| |
Keywords: | : approximation algorithm – multi-commodity flow – network flow – routing – unsplittable flow Mathematics Subject Classification (1991): 90C27 90B10 90C35 05C38 05C85 |
本文献已被 SpringerLink 等数据库收录! |
|