We study an integral counterpart of the classical Maximum Concurrent Flow problem, that we call Integral Concurrent Flow (ICF). In the basic version of this problem (basic-ICF), we are given an undirected n-vertex graph G with edge capacities c(e), a subset T of vertices called terminals, and a demand D(t,t') for every pair (t.t') of the terminals. The goal is to find a maximum value A. and a collection P of paths, such that every pair (t,t') of terminals is connected by 「λ · D(t.t')」 paths in P, and the number of paths containing any edge e is at most c(e). We show an algorithm that achieves a poly log n-approximation for basic-ICF. while violating the edge capacities by only a constant factor. We complement this result by proving that no efficient algorithm can achieve a factor α-approximation with congestion c for anv values α,c satisfying α · c = O(log log n/log log log n). unless NP is contained in ZPTIME(n~(poly log n)). We then turn to study the more general group version of the problem (group-ICF), in which we are given a collection {(S_1,T_1),...,(S_k,T_k)} of pairs of vertex subsets, and for each 1 ≤ i ≤ k. a demand D_i is specified. The goal is to find a maximum value A and a collection P of paths, such that for each i, at least 「λ-D_i」 paths connect the vertices of S_i to the vertices of T_i, while respecting the edge capacities. We show that for any 1 ≤ c ≤ O(log log n), no efficient algorithm can achieve a factor O (n~(1/(2~(2c+3))))-approximation with conges- tion c for the problem, unless NP is contained in DTIME(n~O(log log n)). On the other hand, we show an efficient randomized algorithm that finds a poly log n-approximate solution with a constant congestion, if we are guaranteed that the optimal solution contains at least D ≥ k poly log n paths connecting every pair (S_i,T_i).
展开▼
