Name
Title | ||
|---|---|---|
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems |
Abstract | ||
|---|---|---|
While the maximum single-sink unsplittable and confluent flow problems have been studied extensively, algorithmic work has been primarily restricted to the case where one imposes the no-bottleneck assumption (NBA) (that the maximum demand d(max) is at most the minimum capacity u(min). For instance, under the NBA there is a factor-4.43 approximation algorithm due to Dinitz et al. (1999) for the unsplittable flow problem. Under the even stronger assumption of uniform capacities, there is a factor-3 approximation algorithm due to Chen et al. (2007) for the confluent flow problem. We show, however, that unlike the unsplittable flow problem, a constant-factor approximation algorithm cannot be obtained for the single-sink confluent flow problem even with the no-bottleneck assumption. Specifically, we prove that it is N P-hard to approximate single-sink confluent flow to within O(log(1-epsilon)(n)), for any epsilon > 0. The remainder of our results focus upon the setting without the no-bottleneck assumption. Using exponential-size demands, Azar and Regev prove a Omega(m(1-epsilon)) inapproximability result for maximum cardinality single-sink unsplittable flow in directed graphs. We prove that this lower bound applies to undirected graphs, including planar networks (and for confluent flow). This is the first super-constant hardness known for undirected single-sink unsplittable flow. Furthermore, we show Omega(m(1/2-epsilon))-hardness even if all demands and capacities lie within an arbitrarily small range [1,1 +Delta], for Delta > 0. This result is sharp in that if Delta = 0, then it becomes a single-sink maximum edge-disjoint paths problem which can be solved exactly via a maximum flow algorithm. This motivates us to study maximum priority flows for which we show the same inapproximability bound. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.4086/toc.2017.v013a020 | THEORY OF COMPUTING |
Keywords | Field | DocType |
algorithms,complexity theory,multiflow,network flow,unsplittable flow,confluent flow,priority flow | Flow network,Approximation algorithm,Discrete mathematics,Combinatorics,Polynomial,Upper and lower bounds,Directed graph,Cardinality,Greedy algorithm,Maximum flow problem,Mathematics | Journal |
Volume | Issue | ISSN |
13 | 1 | 1557-2862 |
Citations | PageRank | References |
5 | 0.47 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| F. Bruce Shepherd | 1 | 5 | 1.14 |
| Adrian R Vetta | 2 | 8 | 0.88 |