Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems

DOI10.4230/LIPICS.ISAAC.2017.41zbMATH Open1457.68308OpenAlexW2963439954MaRDI QIDQ5136261FDOQ5136261

Authors Hadi Khodabande, Bo Qin, Mordecai J. Golin 

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1709.10307

zbMATH Keywords

optimizationapproximationdynamic flowconfluent flow

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Flows in graphs (05C21)

Abstract: Dynamic Flows were introduced by Ford and Fulkerson in 1958 to model flows over time. They define edge capacities to be the total amount of flow that can enter an edge {em in one time unit}. Each edge also has a length, representing the time needed to traverse it. Dynamic Flows have been used to model many problems including traffic congestion, hop-routing of packets and evacuation protocols in buildings. While the basic problem of moving the maximal amount of supplies from sources to sinks is polynomial time solvable, natural minor modifications can make it NP-hard. One such modification is that flows be confluent, i.e., all flows leaving a vertex must leave along the same edge. This corresponds to natural conditions in, e.g., evacuation planning and hop routing. We investigate the single-sink Confluent Quickest Flow problem. The input is a graph with edge capacities and lengths, sources with supplies and a sink. The problem is to find a confluent flow minimizing the time required to send supplies to the sink. Our main results include: a) Logarithmic Non-Approximability: Directed Confluent Quickest Flows cannot be approximated in polynomial time with an $O(logn)$ approximation factor, unless $P=NP$. b) Polylogarithmic Bicriteria Approximations: Polynomial time $(O(lo{g}^{8}n),O(lo{g}^{2}kappa))$ bicritera approximation algorithms for the Confluent Quickest Flow problem where $kappa$ is the number of sinks, in both directed and undirected graphs. Corresponding results are also developed for the Confluent Maximum Flow over timeproblem. The techniques developed also improve recent approximation algorithms for static confluent flows.

Recommendations

• Meet and merge: approximation algorithms for confluent flows
• Meet and merge: approximation algorithms for confluent flows
• The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems
• Capacitated Confluent Flows: Complexity and Algorithms
• Quickest Flows Over Time

Cites Work

• scientific article; zbMATH DE number 1003275 (Why is no real title available?)
• (Almost) Tight bounds and existence theorems for single-commodity confluent flows
• A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
• A comprehensive survey on the quickest path problem
• An introduction to network flows over time
• Constraint satisfaction, packet routing, and the lovasz local lemma
• Constructing maximal dynamic flows from static flows
• Graph minors. XIII: The disjoint paths problem
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Maximum flows on disjoint paths
• Meet and merge: approximation algorithms for confluent flows
• Multicommodity flows over time: Efficient algorithms and complexity
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Polynomial-time algorithms for special cases of the maximum confluent flow problem
• Routing and capacity optimization for IP networks
• The directed subgraph homeomorphism problem
• The quickest transshipment problem
• Traffic Networks and Flows over Time

Cited In (6)

• The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems
• Polyhedral results on single node variable upper-bound flow models with allowed configurations
• Meet and merge: approximation algorithms for confluent flows
• Stateless Near Optimal Flow Control with Poly-logarithmic Convergence
• Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities
• Convex Combinations of Single Source Unsplittable Flows

This page was built for publication: Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136261)