Article ID: | iaor2003723 |
Country: | Germany |
Volume: | 91 |
Issue: | 3 |
Start Page Number: | 493 |
End Page Number: | 514 |
Publication Date: | Jan 2002 |
Journal: | Mathematical Programming |
Authors: | Skutella M. |
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 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 and Dinitz