Minimum-cost single-source 2-splittable flow

摘要

In the single-source unsplittable flow problem, commodities must be routed simultaneously from a common source vertex to certain sinks in a given directed 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 cost of the solution should not exceed a given budget. An important open question is whether a simultaneous (2,1)-approximation can be achieved for minimizing congestion and cost, i.e., the budget constraint should not be violated. In this note we show that this is possible for the case of 2-splittable flows, i.e., flows where the demand of each commodity is routed along at most two paths. Our result holds under the "no-bottleneck" assumption, i.e., the maximum demand does not exceed the minimum capacity.