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

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

Authors: Hadi Khodabande, Bo Qin, Mordecai J. Golin 

Publication date: 25 November 2020

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.

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

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

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)

Cites Work

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

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)