Autor: F. Bruce Shepherd, Adrian Vetta
Rok vydání: 2017
Předmět:
Zdroj: Theory of Computing. 13:1-25
ISSN: 1557-2862
DOI: 10.4086/toc.2017.v013a020
Popis: We consider the single-sink network flow problem. An instance consists of a capacitated graph (directed or undirected), a sink node t and a set of demands that we want to send to the sink. Here demand i is located at a node si and requests an amount di of flow capacity in order to route successfully. Two standard objectives are to maximise (i) the number of demands (cardinality) and (ii) the total demand (throughput) that can be routed subject to the capacity constraints. Furthermore, we examine these maximisation problems for three specialised types of network flow: unsplittable, confluent and priority flows. In the unsplittable flow problem, we have edge capacities, and the demand for si must be routed on a single path. In the confluent flow problem, we have node capacities, and the final flow must induce a tree. Both of these problems have been studied extensively, primarily in the single-sink setting. However, most of this work imposed the no-bottleneck assumption (that the maximum demand dmax is at most the minimum capacity umin). Given the no-bottleneck assumption, there is a factor 4.43-approximation algorithm due to Dinitz et al. [16] 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. [10] for the confluent flow problem. However, 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 hard in that setting to approximate single-sink confluent flow to within O(log1− (n)), for any > 0. This result applies for both cardinality and throughput objectives even in undirected graphs. The remainder of our results focus upon the setting without the no-bottleneck assumption. There, the only result we are aware of is an Ω(m1− ) inapproximability result of Azar and Regev [3] for cardinality single-sink unsplittable flow in directed graphs. We prove this lower bound applies to undirected graphs, including planar networks. This is the first super-constant hardness known for undirected single-sink unsplittable flow, and apparently the first polynomial hardness for undirected unsplittable flow even for general 1 ar X iv :1 50 4. 00 62 7v 1 [ cs .D S] 2 A pr 2 01 5 (non-single sink) multiflows. We show the lower bound also applies to the cardinality single-sink confluent flow problem. Furthermore, the proof of Azar and Regev requires exponentially large demands. We show that polynomial hardness continues to hold without this restriction, even if all demands and capacities lie within an arbitrarily small range [1, 1 + ∆], for ∆ > 0. This lower bound applies also to the throughput objective. This result is very sharp since if ∆ = 0, then we have an instance of the single-sink maximum edge-disjoint paths problem which can be solved exactly via a maximum flow algorithm. This motivates us to study an intermediary problem, priority flows, that models the transition as ∆ → 0. Here we have unit-demands, each with a priority level. In addition, each edge has a priority level and a routing path for a demand is then restricted to use edges with at least the same priority level. Our results imply a polynomial lower bound for the maximum priority flow problem, even for the case of uniform capacities. Finally, we present greedy algorithms that provide upper bounds which (nearly) match the lower bounds for unsplittable and priority flows. These upper bounds also apply for general multiflows.
Databáze: OpenAIRE
Externí odkaz: