# Approximation algorithms and hardness of integral concurrent flow

Parinya Chalermsook*, Julia Chuzhoy, Alina Ene, Shi Li

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

5 Citations (Scopus)

## 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 STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing 689-708 20 https://doi.org/10.1145/2213977.2214040 Published - 2012 A4 Article in a conference publication ACM Symposium on Theory of Computing - New York, United StatesDuration: 19 May 2012 → 22 May 2012Conference number: 44

### Conference

Conference ACM Symposium on Theory of Computing STOC United States New York 19/05/2012 → 22/05/2012

## Keywords

• integral concurrent flow

## Fingerprint

Dive into the research topics of 'Approximation algorithms and hardness of integral concurrent flow'. Together they form a unique fingerprint.