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.
