## 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(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 λ 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 congestion c for the problem, unless NP ⊆ 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}).

Original language | English |
---|---|

Title of host publication | STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing |

Pages | 689-708 |

Number of pages | 20 |

DOIs | |

Publication status | Published - 2012 |

MoE publication type | A4 Conference publication |

Event | ACM Symposium on Theory of Computing - New York, United States Duration: 19 May 2012 → 22 May 2012 Conference number: 44 |

### Conference

Conference | ACM Symposium on Theory of Computing |
---|---|

Abbreviated title | STOC |

Country/Territory | United States |

City | New York |

Period | 19/05/2012 → 22/05/2012 |

## Keywords

- integral concurrent flow