2015/04/02 by F. Bruce Shepherd, Shepherd, F. Bruce, Adrian Vetta +1 · 2 citations
Computer Science · Economics, Econometrics and Finance · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1504.00627
openalex publication_date 2015/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider single-sink network flow problems. An instance consists of a\ncapacitated graph (directed or undirected), a sink node t and a set of\ndemands that we want to send to the sink. Here demand i is located at a node\nsi and requests an amount di of flow capacity in order to route\nsuccessfully. Two standard objectives are to maximise (i) the number of demands\n(cardinality) and (ii) the total demand (throughput) that can be routed subject\nto the capacity constraints. Furthermore, we examine these maximisation\nproblems for three specialised types of network flow: unsplittable, confluent\nand priority flows.\n In the em unsplittable flow problem (UFP), we have edge capacities, and\nthe demand for si must be routed on a single path. In the em confluent\nflow problem, we have node capacities, and the final flow must induce a tree.\nBoth of these problems have been studied extensively, primarily in the\nsingle-sink setting. However, most of this work imposed the em no-bottleneck\nassumption (that the maximum demand dmax is at most the minimum capacity\numin). Given the no-bottleneck assumption (NBA), there is a factor\n4.43-approximation algorithm due to Dinitz et al. for the unsplittable flow\nproblem. Under the stronger assumption of uniform capacities, there is a factor\n3-approximation algorithm due to Chen et al. for the confluent flow problem.\nHowever, unlike the UFP, we show that a constant factor approximation algorithm\ncannot be obtained for the single-sink confluent flows even bf with the NBA.\n Without NBA, we show that maximum cardinality single-sink UFP is hard to\napproximate to within a factor n.5-\ε even when all demands lie in a\nsmall interval [1,1+\Δ] where \Δ>0 (but has polynomial input size).\nThis is very sharp since when \Δ=0, this becomes a maximum flow problem.\n