Document Open Access Logo

Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems

Authors Mordecai J. Golin, Hadi Khodabande, Bo Qin

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.41.pdf
  • Filesize: 0.59 MB
  • 13 pages

Document Identifiers

Author Details

Mordecai J. Golin
Hadi Khodabande
Bo Qin

Cite As Get BibTex

Mordecai J. Golin, Hadi Khodabande, and Bo Qin. Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.41

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  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(\log n) approximation factor, unless P=NP.
 
b) Polylogarithmic Bicriteria Approximations: Polynomial time (O(\log^8 n), O(\log^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 time problem. The techniques developed also improve recent approximation algorithms for static confluent flows.

Subject Classification

Keywords
  • Optimization
  • Approximation
  • Dynamic Flow
  • Confluent Flow

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Bley. Routing and capacity optimization for IP networks. In Operations Research Proceedings 2007, pages 9-16. Springer, 2008. Google Scholar
  2. J. Chen, R. D. Kleinberg, L. Lovász, R. Rajaraman, R. Sundaram, and A. Vetta. (Almost) tight bounds and existence theorems for single-commodity confluent flows. Journal of the ACM, 54(4):16, 2007. Google Scholar
  3. J. Chen, R. Rajaraman, and R. Sundaram. Meet and merge: Approximation algorithms for confluent flows. In Proceedings of STOC'03, pages 373-382. ACM, 2003. Google Scholar
  4. D. Dressler and M. Strehler. Polynomial-time algorithms for special cases of the maximum confluent flow problem. Discrete Applied Mathematics, 163, Part 2:142-154, 2014. Google Scholar
  5. L. R. Ford and D. R. Fulkerson. Constructing Maximal Dynamic Flows from Static Flows. Operations Research, 6(3):419-433, jun 1958. Google Scholar
  6. S. Fortune, J. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111-121, 1980. Google Scholar
  7. M. Golin, H. Khodabande, and B. Qin. Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems (full version). arXiv, 2017. URL: http://arxiv.org/abs/1709.10307.
  8. V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd, and M. Yannakakis. Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Journal of Computer and System Sciences, 67(3):473-496, 2003. Google Scholar
  9. A. Hall, S. Hippler, and M. Skutella. Multicommodity flows over time: Efficient algorithms and complexity. Theoretical Computer Science, 379(3):387-404, 2007. Google Scholar
  10. D. G. Harris and A. Srinivasan. Constraint satisfaction, packet routing, and the Lovasz Local Lemma. In Proceedings of STOC'13, pages 685-694, New York, NY, USA, 2013. ACM. Google Scholar
  11. B. Hoppe and É. Tardos. Polynomial time algorithms for some evacuation problems. In Proceedings of SODA'94, pages 433-441, 1994. Google Scholar
  12. B. Hoppe and É. Tardos. The quickest transshipment problem. Mathematics of Operations Research, 25(1):36-62, 2000. Google Scholar
  13. N. Kamiyama. Studies on Quickest Flow Problems in Dynamic Networks and Arborescence Problems in Directed Graphs. PhD thesis, Kyoto University, 2009. Google Scholar
  14. V. Kann. Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters, 37(1):27-35, 1991. Google Scholar
  15. E. Köhler, R.H. Möhring, and M. Skutella. Traffic networks and flows over time. In Algorithmics of Large and Complex Networks, pages 166-196. Springer, 2009. Google Scholar
  16. S. G. Kolliopoulos and C. Stein. Improved approximation algorithms for unsplittable flow problems. In Proceedings of FOCS'97, pages 426-436. IEEE, 1997. Google Scholar
  17. S. Mamada, T. Uno, K. Makino, and S. Fujishige. A tree partitioning problem arising from an evacuation problem in tree dynamic networks. Journal of the Operations Research Society of Japan, 48(3):196-206, 2005. Google Scholar
  18. G. Naves, N. Sonnerat, and A. Vetta. Maximum flows on disjoint paths. In Approximation, Randomization, and Combinatorial Optimization, pages 326-337. Springer, 2010. Google Scholar
  19. M. M. B. Pascoal, M. E. V. Captivo, and J. C. N. Clímaco. A comprehensive survey on the quickest path problem. Annals of Operations Research, 147(1):5-21, aug 2006. Google Scholar
  20. N. Robertson and P.D. Seymour. Graph minors .XIII. the disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. Google Scholar
  21. F. B. Shepherd and A. Vetta. The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems. ArXiv, abs/1504.00627, 2015. Google Scholar
  22. F. B. Shepherd, A. Vetta, and G. T. Wilfong. Polylogarithmic approximations for the capacitated single-sink confluent flow problem. In Proceedings of FOCS'15, pages 748-758, 2015. Google Scholar
  23. Martin Skutella. An introduction to network flows over time. In Research Trends in Combinatorial Optimization, pages 451-482. Springer, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact