Document Open Access Logo

Simultaneously Load Balancing for Every p-norm, With Reassignments

Authors Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, Clifford Stein

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.51.pdf
  • Filesize: 468 kB
  • 14 pages

Document Identifiers

Author Details

Aaron Bernstein
Tsvi Kopelowitz
Seth Pettie
Ely Porat
Clifford Stein

Cite AsGet BibTex

Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, and Clifford Stein. Simultaneously Load Balancing for Every p-norm, With Reassignments. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ITCS.2017.51

Abstract

This paper investigates the task of load balancing where the objective function is to minimize the p-norm of loads, for p\geq 1, in both static and incremental settings. We consider two closely related load balancing problems. In the bipartite matching problem we are given a bipartite graph G=(C\cup S, E) and the goal is to assign each client c\in C to a server s\in S so that the p-norm of assignment loads on S is minimized. In the graph orientation problem the goal is to orient (direct) the edges of a given undirected graph while minimizing the p-norm of the out-degrees. The graph orientation problem is a special case of the bipartite matching problem, but less complex, which leads to simpler algorithms. For the graph orientation problem we show that the celebrated Chiba-Nishizeki peeling algorithm provides a simple linear time load balancing scheme whose output is an orientation that is 2-competitive, in a p-norm sense, for all p\geq 1. For the bipartite matching problem we first provide an offline algorithm that computes an optimal assignment. We then extend this solution to the online bipartite matching problem with reassignments, where vertices from C arrive in an online fashion together with their corresponding edges, and we are allowed to reassign an amortized O(1) vertices from C each time a new vertex arrives. In this online scenario we show how to maintain a single assignment that is 8-competitive, in a p-norm sense, for all p\geq 1.
Keywords
  • Online Matching
  • Graph Orientation
  • Minmizing the p-norm

Metrics

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

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: http://dx.doi.org/10.1145/210332.210337.
  2. Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom. Mind the gap: Essentially optimal algorithms for online dictionary matching with one gap. In Accepted to International Symposium on Algorithms and Computation (ISAAC), 2016. Google Scholar
  3. Yossi Azar, Joseph Naor, and Raphael Rom. The competitiveness of on-line assignments. In SODA: ACM-SIAM Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms), 1992. Google Scholar
  4. Glencora Borradaile, Jennifer Iglesias, Theresa Migler, Antonio Ochoa, Gordon T. Wilfong, and Lisa Zhang. Egalitarian graph orientations. CoRR, abs/1212.2178, 2012. Google Scholar
  5. Gerth Stølting Brodal and Rolf Fagerberg. Dynamic representation of sparse graphs. In Algorithms and Data Structures, 6th International Workshop, WADS, pages 342-351, 1999. URL: http://dx.doi.org/10.1007/3-540-48447-7_34.
  6. Julie Anne Cain, Peter Sanders, and Nick Wormald. The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation. In 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 469-476. SIAM, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283433.
  7. Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14(1):210-223, 1985. Google Scholar
  8. Marek Chrobak and David Eppstein. Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci., 86(2):243-266, 1991. URL: http://dx.doi.org/10.1016/0304-3975(91)90020-3.
  9. Zdenek Dvorak and Vojtech Tuma. A dynamic data structure for counting subgraphs in sparse graphs. In Algorithms and Data Structures - 13th International Symposium, WADS, pages 304-315, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40104-6_27.
  10. David Eisenstat, Philip N. Klein, and Claire Mathieu. An efficient polynomial-time approximation scheme for steiner forest in planar graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 626-638, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095169.
  11. David Eppstein. All maximal independent sets and dynamic dominance for sparse graphs. ACM Transactions on Algorithms, 5(4), 2009. URL: http://dx.doi.org/10.1145/1597036.1597042.
  12. Leah Epstein and Asaf Levin. Robust algorithms for preemptive scheduling. In ESA, volume 6942 of Lecture Notes in Comput. Sci., pages 567-578. Springer, Heidelberg, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_48.
  13. Rudolf Fleischer and Michaela Wahl. Online scheduling revisited. In Proceedings of the 8th Annual European Symposium on Algorithms, ESA '00, pages 202-210, London, UK, UK, 2000. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=647910.740462.
  14. Ashish Goel, Adam Meyerson, and Serge A. Plotkin. Combining fairness with throughput: online routing with multiple objectives. In STOC, pages 670-679, 2000. Google Scholar
  15. Albert Gu, Anupam Gupta, and Amit Kumar. The power of deferral: maintaining a constant-competitive steiner tree online. In STOC, pages 525-534, 2013. Google Scholar
  16. Anupam Gupta, Amit Kumar, and Cliff Stein. Maintaining assignments online: Matching, scheduling, and flows. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 468-479, 2014. Google Scholar
  17. Meng He, Ganggui Tang, and Norbert Zeh. Orienting dynamic graphs, with applications to maximal matchings and adjacency queries. In ISAAC, pages 128-140, 2014. Google Scholar
  18. Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem. SIAM J. Discrete Math., 4(3):369-384, 1991. Google Scholar
  19. Jon M. Kleinberg, Yuval Rabani, and Éva Tardos. Fairness in routing and load balancing. J. Comput. Syst. Sci., 63(1):2-20, 2001. Google Scholar
  20. Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon. Orienting fully dynamic graphs with worst-case time bounds. In ICALP (2), pages 532-543, 2014. Google Scholar
  21. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Dynamic set intersection. In Proceedings 14th Int'l Symposium on Algorithms and Data Structures (WADS), pages 470-481, 2015. Google Scholar
  22. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In SODA, pages 1272-1287, 2016. Google Scholar
  23. Lukasz Kowalik. Adjacency queries in dynamic sparse graphs. Inf. Process. Lett., 102(5):191-195, 2007. URL: http://dx.doi.org/10.1016/j.ipl.2006.12.006.
  24. Lukasz Kowalik and Maciej Kurowski. Oracles for bounded-length shortest paths in planar graphs. ACM Transactions on Algorithms, 2(3):335-363, 2006. URL: http://dx.doi.org/10.1145/1159892.1159895.
  25. R. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In ACM EC, 2004. Google Scholar
  26. Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese. The power of recourse for online MST and TSP. In ICALP (1), pages 689-700, 2012. Google Scholar
  27. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. In Proceedings of the 45th ACM Symposium on Theory of Computing, STOC, pages 745-754, 2013. URL: http://dx.doi.org/10.1145/2488608.2488703.
  28. S. Phillips and J. Westbrook. On-line load balancing and network flow. Algorithmica, 21(3):245-261, 1998. URL: http://dx.doi.org/10.1007/PL00009214.
  29. John F. Rudin, III and R. Chandrasekaran. Improved bounds for the online scheduling problem. SIAM J. Comput., 32(3):717-735, March 2003. URL: http://dx.doi.org/10.1137/S0097539702403438.
  30. Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online scheduling with bounded migration. Math. Oper. Res., 34(2):481-498, 2009. URL: http://dx.doi.org/10.1287/moor.1090.0381.
  31. Stephen. B. Seidman. Network structure and minimum degree. Social Networks, 5(3):269-287, 1983. Google Scholar
  32. Martin Skutella and José Verschae. A robust PTAS for machine covering and packing. In ESA (I), volume 6346 of LNCS, pages 36-47. Springer, Berlin, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15775-2_4.
  33. Jeffery Westbrook. Load balancing for response time. J. Algorithms, 35(1):1-16, 2000. URL: http://dx.doi.org/10.1006/jagm.2000.1074.
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