Document Open Access Logo

All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method

Authors Sepehr Assadi, Aaron Bernstein, Zachary Langley

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.7.pdf
  • Filesize: 0.82 MB
  • 24 pages

Document Identifiers

Author Details

Sepehr Assadi
  • Rutgers University, New Brunswick, NJ, USA
Aaron Bernstein
  • Rutgers University, New Brunswick, NJ, USA
Zachary Langley
  • Rutgers University, New Brunswick, NJ, USA

Funding

  • Assadi, Sepehr: Research supported in part by NSF CAREER Award CCF-2047061, a Google Research gift, and a Fulcrum award from Rutgers Research Council.
  • Bernstein, Aaron: Research supported in part by NSF CAREER Award CCF-1942010.

Cite As Get BibTex

Sepehr Assadi, Aaron Bernstein, and Zachary Langley. All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.7

Abstract

In the weighted load balancing problem, the input is an n-vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real weight. The output is an assignment that maps each client to one of its adjacent servers, and the load of a server is then the sum of the weights of the clients assigned to it. The goal is to find an assignment that is well-balanced, typically captured by (approximately) minimizing either the 𝓁_∞- or 𝓁₂-norm of the server loads. Generalizing both of these objectives, the all-norm load balancing problem asks for an assignment that approximately minimizes all 𝓁_p-norm objectives for p ≥ 1, including p = ∞, simultaneously.
Our main result is a deterministic O(log n)-pass O(1)-approximation semi-streaming algorithm for the all-norm load balancing problem. Prior to our work, only an O(log n)-pass O(log n)-approximation algorithm for the 𝓁_∞-norm objective was known in the semi-streaming setting.
Our algorithm uses a novel application of the multiplicative weights update method to a mixed covering/packing convex program for the all-norm load balancing problem involving an infinite number of constraints.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Load Balancing
  • Semi-Streaming Algorithms
  • Semi-Matching

Metrics

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

Related Versions

References

  1. Kook Jin Ahn and Sudipto Guha. Linear programming in the semi-streaming model with application to the maximum matching problem. In 38th International Colloquium on Automata, Languages, and Programming, pages 526-538, 2011. Google Scholar
  2. Noga Alon, Yossi Azar, Gerhard J. Woeginger, and Tal Yadid. Approximation schemes for scheduling. In Proc. 8th Ann. ACM-SIAM Symposium on Discrete Algorithms, pages 493-500, 1997. Google Scholar
  3. Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of computing, 8(1):121-164, 2012. Google Scholar
  4. Sepehr Assadi. Tight space-approximation tradeoff for the multi-pass streaming set cover problem. In Proc. 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 321-335, 2017. URL: https://doi.org/10.1145/3034786.3056116.
  5. Sepehr Assadi and Soheil Behnezhad. Beating two-thirds for random-order streaming matching. In Proc. 48th Ann. International Colloquium on Automata, Languages, and Programming, volume 198, pages 19:1-19:13, 2021. Google Scholar
  6. Sepehr Assadi, Aaron Bernstein, and Zachary Langley. Improved bounds for distributed load balancing. In Proc. 34th Int'l Symposium on Distributed Computing (DISC), volume 179 of LIPIcs, pages 1:1-1:15, 2020. Google Scholar
  7. Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Semi-streaming bipartite matching in fewer passes and optimal space. In Proc. 33rd Ann. ACM-SIAM Symposium on Discrete Algorithms, pages 627-669, 2022. Google Scholar
  8. Sepehr Assadi, S. Cliff Liu, and Robert E. Tarjan. An auction algorithm for bipartite matching in streaming and massively parallel computation models. In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 165-171, 2021. Google Scholar
  9. Sepehr Assadi and Ran Raz. Near-quadratic lower bounds for two-pass graph streaming algorithms. In Proc. 61st Ann. IEEE Symposium on Foundations of Computer Science, pages 342-353, 2020. Google Scholar
  10. Yossi Azar, Leah Epstein, Yossi Richter, and Gerhard J. Woeginger. All-norm approximation algorithms. J. Algorithms, 52(2):120-133, 2004. URL: https://doi.org/10.1016/j.jalgor.2004.02.003.
  11. Leonid Barenboim and Gal Oren. Distributed backup placement in one round and its applications to maximum matching and self-stabilization. In Proc. 3rd Symposium on Simplicity in Algorithms, pages 99-105, 2020. URL: https://doi.org/10.1137/1.9781611976014.14.
  12. MohammadHossein Bateni, Hossein Esfandiari, and Vahab S. Mirrokni. Almost optimal streaming algorithms for coverage problems. In Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures, pages 13-23, 2017. URL: https://doi.org/10.1145/3087556.3087585.
  13. Aaron Bernstein. Improved bounds for matching in random-order streams. In 47th International Colloquium on Automata, Languages, and Programming, pages 12:1-12:13, 2020. Google Scholar
  14. Aaron Bernstein, Aditi Dudeja, and Zachary Langley. A framework for dynamic matching in weighted graphs. In Proc. 53rd Ann. ACM Symposium on Theory of Computing, pages 668-681, 2021. Google Scholar
  15. Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, and Clifford Stein. Simultaneously load balancing for every p-norm, with reassignments. In Proc. 8th Innovations in Theoretical Computer Science Conference, volume 67 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 51,14, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.51.
  16. Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Dynamic algorithms for packing-covering LPs via multiplicative weight updates. CoRR, abs/2207.07519, 2022. Google Scholar
  17. J. Bruno, E. G. Coffman, Jr., and R. Sethi. Scheduling independent tasks to reduce mean finishing time. Comm. ACM, 17:382-387, 1974. URL: https://doi.org/10.1145/361011.361064.
  18. Deeparnab Chakrabarty and Chaitanya Swamy. Simpler and better algorithms for minimum-norm load balancing. In Proc. 27th Ann. European Symposium on Algorithms, volume 144 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 27,12, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.27.
  19. Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. Almost optimal super-constant-pass streaming lower bounds for reachability. In Proc. 53rd Ann. ACM Symposium on Theory of Computing, pages 570-583, 2021. Google Scholar
  20. Michael Crouch and Daniel M. Stubbs. Improved streaming algorithms for weighted matching, via unweighted matching. In Proc. 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, volume 28, pages 96-104, 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.96.
  21. Andrzej Czygrinow, Michal Hanćkowiak, Edyta Szymańska, and Wojciech Wawrzyniak. Distributed 2-approximation algorithm for the semi-matching problem. In Proc. 26th International Symposium on Distributed Computing, volume 7611 of LNCS, pages 210-222, 2012. URL: https://doi.org/10.1007/978-3-642-33651-5_15.
  22. Jittat Fakcharoenphol, Bundit Laekhanukit, and Danupon Nanongkai. Faster algorithms for semi-matching problems. ACM Trans. Algorithms, 10(3):Art. 14,23, 2014. URL: https://doi.org/10.1145/2601071.
  23. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. In Proc. 31st Ann. International Colloquium on Automata, Languages, and Programming, volume 3142 of Lecture Notes in Computer Science, pages 531-543, 2004. Google Scholar
  24. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theor. Comput. Sci., 348(2-3):207-216, 2005. Google Scholar
  25. Manuela Fischer, Slobodan Mitrovic, and Jara Uitto. Deterministic (1+ε)-approximate maximum matching with poly(1/ε) passes in the semi-streaming model. In Proc. 54th Ann. ACM Symposium on Theory of Computing, pages 248-260, 2022. Google Scholar
  26. Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In Proc. 23rd Ann. ACM-SIAM Symposium on Discrete Algorithms, pages 468-485, 2012. Google Scholar
  27. Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph processing. Algorithmica, 76(3):654-683, 2016. Google Scholar
  28. Magnús M. Halldórsson, Sven Köhler, Boaz Patt-Shamir, and Dror Rawitz. Distributed backup placement in networks. Distrib. Comput., 31(2):83-98, 2018. URL: https://doi.org/10.1007/s00446-017-0299-x.
  29. Nicholas J. A. Harvey, Richard E. Ladner, László Lovász, and Tami Tamir. Semi-matchings for bipartite graphs and load balancing. J. Algorithms, 59(1):53-78, 2006. URL: https://doi.org/10.1016/j.jalgor.2005.01.003.
  30. W. A. Horn. Minimizing average flow time with parallel machines. Oper. Res., 21(3), 1973. URL: https://doi.org/10.1287/opre.21.3.846.
  31. Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan R. Ullman, Ali Vakilian, and Anak Yodpinyanee. Fractional set cover in the streaming model. In Proc. 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, volume 81 of LIPIcs, pages 12:1-12:20, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.12.
  32. Michael Kapralov. Better bounds for matchings in the streaming model. In Proc. 24th Ann. ACM-SIAM Symposium on Discrete Algorithms, pages 1679-1697, 2013. Google Scholar
  33. Michael Kapralov. Space lower bounds for approximating maximum matching in the edge arrival model. In Proc. 32nd Ann. ACM-SIAM Symposium on Discrete Algorithms, pages 1874-1893, 2021. Google Scholar
  34. Christian Konrad, Frédéric Magniez, and Claire Mathieu. Maximum matching in semi-streaming with few passes. In Proc. 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 231-242, 2012. Google Scholar
  35. Christian Konrad and Adi Rosén. Approximating semi-matchings in streaming and in two-party communication. ACM Trans. Algorithms, 12(3):Art. 32,21, 2016. URL: https://doi.org/10.1145/2898960.
  36. Anshul Kothari, Subhash Suri, Csaba D. Tóth, and Yunhong Zhou. Congestion games, load balancing, and price of anarchy. In Proc. 1st Combinatorial and Algorithmic Aspects of Networking, volume 3405 of LNCS, pages 13-27, 2004. URL: https://doi.org/10.1007/11527954_3.
  37. Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in mapreduce. In Proc. 23rd Ann. ACM Symposium on Parallelism in Algorithms and Architectures, pages 85-94, 2011. URL: https://doi.org/10.1145/1989493.1989505.
  38. Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approximation algorithms for scheduling unrelated parallel machines. In Proc. 28th Ann. IEEE Symposium on Foundations of Computer Science, pages 217-224, 1987. URL: https://doi.org/10.1109/SFCS.1987.8.
  39. Yixun Lin and Wenhua Li. Parallel machine scheduling of machine-dependent jobs with unit-length. European J. Oper. Res., 156(1):261-266, 2004. URL: https://doi.org/10.1016/S0377-2217(02)00914-1.
  40. Renita Machado and Sirin Tekinay. A survey of game-theoretic approaches in wireless sensor networks. Comput. Networks, 52(16):3047-3061, 2008. URL: https://doi.org/10.1016/j.gaceta.2008.07.003.
  41. Andrew McGregor. Finding graph matchings in data streams. In Proc. 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 170-181, 2005. Google Scholar
  42. Andrew McGregor and Hoa T. Vu. Better streaming algorithms for the maximum coverage problem. In Proc. 20th International Conference on Database Theory, volume 68 of LIPIcs, pages 22:1-22:18, 2017. URL: https://doi.org/10.4230/LIPIcs.ICDT.2017.22.
  43. Gal Oren, Leonid Barenboim, and Harel Levin. Distributed fault-tolerant backup-placement in overloaded wireless sensor networks. In Proc. 9th International Conference on Broadband Communications, Networks, and Systems, pages 212-224, 2018. URL: https://doi.org/10.1007/978-3-030-05195-2_21.
  44. Narayanan Sadagopan, Mitali Singh, and Bhaskar Krishnamachari. Decentralized utility-based sensor network design. Mobile Networks and Applications, 11(3):341-350, 2006. URL: https://doi.org/10.1007/s11036-006-5187-8.
  45. Thatchaphol Saranurak. Private communication, September 2022. Google Scholar
  46. Subhash Suri, Csaba D. Tóth, and Yunhong Zhou. Selfish load balancing and atomic congestion games. Algorithmica, 47(1):79-96, 2004. URL: https://doi.org/10.1007/s00453-006-1211-4.
  47. Subhash Suri, Csaba D. Tóth, and Yunhong Zhou. Uncoordinated load balancing and congestion games in P2P systems. In Proc. 3rd International Workshop on Peer-to-Peer Systems, pages 123-130, 2004. URL: https://doi.org/10.1007/978-3-540-30183-7_12.
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