Document Open Access Logo

A Simple Boosting Framework for Transshipment

Author Goran Zuzic

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.104.pdf
  • Filesize: 0.85 MB
  • 14 pages

Document Identifiers

Author Details

Goran Zuzic
  • Google Research, Zürich, Switzerland
  • ETH Zürich, Switzerland

Funding

  • Zuzic, Goran: Work presented in this paper was partially performed while at ETH Zürich. Supported in part by NSF grants CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808, a Sloan Research Fellowship, and funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No. 949272).

Acknowledgements

The author would like to thank Bernhard Haeupler, Patrik Pavic, and Richard Peng for helpful discussions about the paper. The author would also like to thank the anonymous reviewers for their helpful suggestions that significantly improved the quality of the paper.

Cite AsGet BibTex

Goran Zuzic. A Simple Boosting Framework for Transshipment. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 104:1-104:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.104

Abstract

Transshipment is an important generalization of both the shortest path problem and the optimal transport problem. The task asks to route a demand using a flow of minimum cost over (uncapacitated) edges. Transshipment has recently received extensive attention in theoretical computer science as it is the centerpiece of all modern theoretical breakthroughs in parallel and distributed (approximate) shortest-path computation, a classic and well-studied problem. The key advantage of transshipment over shortest paths is the so-called boosting property: one can often boost a crude approximate solution to a (near-optimal) (1+ε)-approximate solution. However, our understanding of this phenomenon is limited: it is not clear which approximators can be boosted. Moreover, all current boosting frameworks are built with a specific type of approximator in mind and are relatively complicated. The main takeaway of our paper is conceptual: any black-box oracle that computes an approximate dual solution can be boosted to an (1+ε)-approximator. This decouples and simplifies all known near-optimal (1+ε)-approximate transshipment and shortest paths results: they all (implicitly) construct approximate dual solutions and boost them. We provide a very simple analysis based on the multiplicative weights framework. Furthermore, to keep the paper completely self-contained, we provide a new (and arguably much simpler) analysis of multiplicative weights that leverages well-known optimization tools to bypass the ad-hoc calculations used in the standard analyses.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Mathematical optimization
  • Theory of computation → Mixed discrete-continuous optimization
  • Theory of computation → Shortest paths
  • Theory of computation → Parallel algorithms
Keywords
  • mixed continuous-discrete optimization
  • boosting
  • multiplicative weights
  • theoretical computer science
  • shortest path
  • parallel algorithms

Metrics

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

Related Versions

References

  1. Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva. Iterative refinement for 𝓁_p-norm regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1405-1424. SIAM, 2019. Google Scholar
  2. Alexandr Andoni, Clifford Stein, and Peilin Zhong. Parallel approximate undirected shortest paths via low hop emulators. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 322-335. ACM, 2020. Google Scholar
  3. Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory Comput., 8(1):121-164, 2012. Google Scholar
  4. 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. Google Scholar
  5. 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), volume 91, pages 7:1-7:16, 2017. Google Scholar
  6. Jean Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52(1-2):46-52, 1985. Google Scholar
  7. Sanjoy Dasgupta and Anupam Gupta. An elementary proof of the johnson-lindenstrauss lemma. International Computer Science Institute, Technical Report, 22(1):1-5, 1999. Google Scholar
  8. Bernhard Haeupler and Jason Li. Faster distributed shortest path approximations via shortcuts. arXiv preprint, 2018. URL: https://arxiv.org/abs/1802.03671.
  9. Piotr Indyk and Nitin Thaper. Fast image retrieval via embeddings. In 3rd international workshop on statistical and computational theories of vision, volume 2(3), page 5, 2003. Google Scholar
  10. Jason Li. Faster parallel algorithm for approximate shortest path. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 308-321. ACM, 2020. Google Scholar
  11. Aleksander Madry. Fast approximation algorithms for cut-based problems in undirected graphs. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 245-254, 2010. Google Scholar
  12. David Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000. Google Scholar
  13. Richard Peng. Approximate undirected maximum flows in O (m polylog (n)) time. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1862-1867, 2016. Google Scholar
  14. Lyle Ramshaw and Robert E Tarjan. On minimum-cost assignments in unbalanced bipartite graphs. HP Labs, Palo Alto, CA, USA, Tech. Rep. HPL-2012-40R1, 20, 2012. Google Scholar
  15. Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li. Undirected (1+epsilon)-shortest paths via minor-aggregates: Near-optimal deterministic parallel & distributed algorithms. In Proceedings of the 54rd Annual ACM Symposium on Theory of Computing (STOC), 2022. Google Scholar
  16. Jonah Sherman. Nearly maximum flows in nearly linear time. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 263-269, 2013. Google Scholar
  17. Jonah Sherman. Generalized preconditioning and undirected minimum-cost flow. In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 772-780, 2017. Google Scholar
  18. Cédric Villani et al. Optimal transport: old and new, volume 338. Springer, 2009. Google Scholar
  19. Goran Zuzic, Goramoz Goranci, Mingquan Ye, Bernhard Haeupler, and Xiaorui Sun. Universally-optimal distributed shortest paths and transshipment via graph-based l1-oblivious routing. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2022. 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 Imprint Privacy Contact