Abstract | ||
---|---|---|
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 λ, 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 any values α,c satisfying α ⋅ c=O(log log n/log log log n), unless NP ⊆ ZPTIME(npoly log n). We then turn to study the more general group version of the problem (group=ICF), in which we are given a collection (S1,T1),...,(Sk,Tk)} of pairs of vertex subsets, and for each 1 ≤ i ≤ k, a demand Di is specified. The goal is to find a maximum value λ and a collection P of paths, such that for each i, at least ⌊ λ ⋅ Di⌋ paths connect the vertices of Si to the vertices of Ti, while respecting the edge capacities. We show that for any 1 ≤ c ≤ O(log log n), no efficient algorithm can achieve a factor O(n1/(22c+3))-approximation with congestion c for the problem, unless NP ⊆ DTIME(nO(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 (Si,Ti). |
Year | DOI | Venue |
---|---|---|
2012 | 10.1145/2213977.2214040 | STOC |
Keywords | Field | DocType |
log log n,npoly log n,edge capacity,poly log n-approximate solution,congestion c,collection p,integral concurrent flow,poly log n-approximation,approximation algorithm,efficient algorithm,log log log n,k poly log n,randomized algorithm,satisfiability | Log-log plot,Randomized algorithm,Discrete mathematics,Binary logarithm,Approximation algorithm,DTIME,Graph,Combinatorics,Vertex (geometry),Mathematics | Conference |
Citations | PageRank | References |
1 | 0.36 | 26 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Parinya Chalermsook | 1 | 187 | 20.94 |
Julia Chuzhoy | 2 | 683 | 38.65 |
Alina Ene | 3 | 409 | 25.47 |
Shi Li | 4 | 208 | 22.01 |