Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

Authors Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, Christoph Lenzen



PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.7.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Ruben Becker
Andreas Karrenbauer
Sebastian Krinninger
Christoph Lenzen

Cite AsGet BibTex

Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.7

Abstract

We present a method for solving the shortest transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of (1 + epsilon) in undirected graphs with non-negative integer edge weights using a tailored gradient descent algorithm. Our gradient descent algorithm takes epsilon^(-3) polylog(n) iterations, and in each iteration it needs to solve an instance of the transshipment problem up to a multiplicative error of polylog(n), where n is the number of nodes. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a careful white-box analysis, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve prior work by obtaining the following results: (1) Broadcast CONGEST model: (1 + epsilon)-approximate SSSP using ~O((sqrt(n) + D) epsilon^(-O(1))) rounds, where D is the (hop) diameter of the network. (2) Broadcast congested clique model: (1 + epsilon)-approximate shortest transshipment and SSSP using ~O(epsilon^(-O(1))) rounds. (3) Multipass streaming model: (1 + epsilon)-approximate shortest transshipment and SSSP using ~O(n) space and ~O(epsilon^(-O(1))) passes. The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative integer edge weights that are polynomially bounded in n; for general non-negative weights, running times scale with the logarithm of the maximum ratio between non-zero weights. In case of asymmetric costs for traversing an edge in opposite directions, running times scale with the maximum ratio between the costs of both directions over all edges.
Keywords
  • Shortest Paths
  • Shortest Transshipment
  • Undirected Min-cost Flow
  • Gradient Descent
  • Spanner

Metrics

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

References

  1. Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear additive spanners. In Symposium on Discrete Algorithms (SODA), pages 568-576, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.36.
  2. Yair Bartal. On approximating arbitrary metrices by tree metrics. In Symposium on the Theory of Computing (STOC), pages 161-168, 1998. URL: http://dx.doi.org/10.1145/276698.276725.
  3. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures &Algorithms, 30(4):532-563, 2007. Announced at ICALP'03. URL: http://dx.doi.org/10.1002/rsa.20130.
  4. Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87-90, 1958. Google Scholar
  5. Aaron Bernstein. Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time. In Symposium on Foundations of Computer Science (FOCS), pages 693-702, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.16.
  6. Gerth Stølting Brodal, Jesper Larsson Träff, and Christos D. Zaroliagis. A parallel priority queue with constant time operations. Journal of Parallel and Distributed Computing, 49(1):4-21, 1998. Announced at IPPS'97. URL: http://dx.doi.org/10.1006/jpdc.1998.1425.
  7. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. In Symposium on Principles of Distributed Computing (PODC), pages 143-152, 2015. URL: http://dx.doi.org/10.1145/2767386.2767414.
  8. Paul Christiano, Jonathan A. Kelner, Aleksander Mądry, Daniel A. Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Symp. on Theory of Computing (STOC), pages 273-282, 2011. URL: http://dx.doi.org/10.1145/1993636.1993674.
  9. Edith Cohen. Using selective path-doubling for parallel shortest-path computations. Journal of Algorithms, 22(1):30-56, 1997. Announced at ISTCS'93. URL: http://dx.doi.org/10.1006/jagm.1996.0813.
  10. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. Journal of the ACM, 47(1):132-166, 2000. Announced at STOC'94. URL: http://dx.doi.org/10.1145/331605.331610.
  11. Michael B. Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu. Negative-weight shortest paths and unit capacity minimum cost flow in Õ(m^10/7 log W) time. In Symposium on Discrete Algorithms (SODA), 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.48.
  12. Samuel I. Daitch and Daniel A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Symposium on Theory of Computing (STOC), pages 451-460, 2008. URL: http://dx.doi.org/10.1145/1374376.1374441.
  13. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM Journal on Computing, 41(5):1235-1265, 2012. Announced at STOC'11. URL: http://dx.doi.org/10.1137/11085178X.
  14. Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248-264, 1972. URL: http://dx.doi.org/10.1145/321694.321699.
  15. Michael Elkin. Distributed exact shortest paths in sublinear time. In Symposium on the Theory of Computing (STOC), pages 757-770, 2017. URL: http://dx.doi.org/10.1145/3055399.3055452.
  16. Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. Lower-stretch spanning trees. SIAM Journel on Computing, 38(2):608-628, 2008. Announced at STOC'05. URL: http://dx.doi.org/10.1137/050641661.
  17. Michael Elkin and Ofer Neiman. Hopsets with constant hopbound, and applications to approximate shortest paths. In Symposium on Foundations of Computer Science (FOCS), pages 128-137, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.22.
  18. Michael Elkin and Ofer Neiman. Linear-size hopsets with small hopbound, and distributed routing with low memory. CoRR, abs/1704.08468, 2017. URL: https://arxiv.org/abs/1704.08468.
  19. Lester R. Ford. Network flow theory. Technical Report P-923, The RAND Corporation, 1956. Google Scholar
  20. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, 1987. Announced at FOCS'84. URL: http://dx.doi.org/10.1145/28869.28874.
  21. Andrew V. Goldberg. Scaling algorithms for the shortest paths problem. SIAM Journal on Computing, 24(3):494-504, 1995. Announced at SODA'93. URL: http://dx.doi.org/10.1137/S0097539792231179.
  22. Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph processing. In Conference on Computational Complexity (CCC), pages 287-298, 2013. URL: http://dx.doi.org/10.1109/CCC.2013.37.
  23. Thomas Dueholm Hansen, Haim Kaplan, Robert Endre Tarjan, and Uri Zwick. Hollow heaps. In International Colloquium on Automata, Languages and Programming (ICALP), pages 689-700, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_56.
  24. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In Symposium on Foundations of Computer Science (FOCS), pages 146-155, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.24.
  25. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Symposium on Theory of Computing (STOC), pages 489-498, 2016. URL: http://dx.doi.org/10.1145/2897518.2897638.
  26. Shang-En Huang and Seth Pettie. Thorup-Zwick emulators are universally optimal hopsets. CoRR, abs/1705.00327, 2017. URL: https://arxiv.org/abs/1705.00327.
  27. Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Symposium on Discrete Algorithms (SODA), pages 217-226, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.16.
  28. Philip N. Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms, 25(2):205-220, 1997. Announced at STOC'92. URL: http://dx.doi.org/10.1006/jagm.1997.0888.
  29. Bernhard Korte and Jens Vygen. Combinatorial Optimization. Springer, 2000. Google Scholar
  30. François Le Gall. Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems. In International Symposium on Distributed Computing (DISC), pages 57-70, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53426-7_5.
  31. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in Õ(√ rank) iterations and faster algorithms for maximum flow. In Symposium on Foundations of Computer Science (FOCS), pages 424-433, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.52.
  32. Gary L. Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved parallel algorithms for spanners and hopsets. In Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 192-201, 2015. URL: http://dx.doi.org/10.1145/2755573.2755574.
  33. Aleksander Mądry. Navigating central path with electrical flows: From flows to matchings, and back. In Symposium on Foundations of Computer Science (FOCS), pages 253-262, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.35.
  34. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Symposium on Theory of Computing (STOC), pages 565-573, 2014. URL: http://dx.doi.org/10.1145/2591796.2591850.
  35. James B. Orlin. A faster strongly polynomial minimum cost flow algorithm. Operations Research, 41(2):338-350, 1993. Announced at STOC'88. URL: http://dx.doi.org/10.1287/opre.41.2.338.
  36. Alexander Schrijver. Combinatorial Optimization. Springer, 2003. Google Scholar
  37. Jonah Sherman. Nearly maximum flows in nearly linear time. In Symposium on Foundations of Computer Science (FOCS), pages 263-269, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.36.
  38. Jonah Sherman. Generalized preconditioning and network flow problems. In Symposium on Discrete Algorithms (SODA), pages 772-780, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.49.
  39. Hanmao Shi and Thomas H. Spencer. Time-work tradeoffs of the single-source shortest paths problem. Journal of Algorithms, 30(1):19-32, 1999. URL: http://dx.doi.org/10.1006/jagm.1998.0968.
  40. Thomas H. Spencer. Time-work tradeoffs for parallel algorithms. Journal of the ACM, 44(5):742-778, 1997. Announced at SODA'91 and SPAA'91. URL: http://dx.doi.org/10.1145/265910.265923.
  41. Mikkel Thorup. Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM, 46(3):362-394, 1999. Announced at FOCS'97. URL: http://dx.doi.org/10.1145/316542.316548.
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