Approximating the single source unsplittable min-cost flow problem

Approximating the single source unsplittable min-cost flow problem

0.00 Avg rating0 Votes
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:
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 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 et al. 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.

Reviews

Required fields are marked *. Your email address will not be published.