Document Open Access Logo

Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments

Authors Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep, Janani Sundaresan

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.65.pdf
  • Filesize: 0.74 MB
  • 17 pages

Document Identifiers

Author Details

Varun Gupta
  • Booth School of Business, University of Chicago, IL, USA
Ravishankar Krishnaswamy
  • Microsoft Research, Bengaluru, India
Sai Sandeep
  • University of California, Berkeley, CA, USA
Janani Sundaresan
  • Department of Computer Science, Rutgers University, Piscataway, NJ, USA

Funding

  • Sandeep, Sai: Work supported in part by NSF grant CCF-2228287.
  • Sundaresan, Janani: Work partly supported by Microsoft Research India.

Acknowledgements

We want to thank the anonymous reviewers at ITCS for their helpful comments and suggestions.

Cite AsGet BibTex

Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep, and Janani Sundaresan. Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 65:1-65:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.65

Abstract

In this paper we study two fully-dynamic multi-dimensional vector load balancing problems with recourse. The adversary presents a stream of n job insertions and deletions, where each job j is a vector in ℝ^d_{≥ 0}. In the vector scheduling problem, the algorithm must maintain an assignment of the active jobs to m identical machines to minimize the makespan (maximum load on any dimension on any machine). In the vector bin packing problem, the algorithm must maintain an assignment of active jobs into a number of bins of unit capacity in all dimensions, to minimize the number of bins currently used. In both problems, the goal is to maintain solutions that are competitive against the optimal solution for the active set of jobs, at every time instant. The algorithm is allowed to change the assignment from time to time, with the secondary objective of minimizing the amortized recourse, which is the average cardinality of the change of the assignment per update to the instance. For the vector scheduling problem, we present two simple algorithms. The first is a randomized algorithm with an O(1) amortized recourse and an O(log d/log log d) competitive ratio against oblivious adversaries. The second algorithm is a deterministic algorithm that is competitive against adaptive adversaries but with a slightly higher competitive ratio of O(log d) and a per-job recourse guarantee bounded by Õ(log n + log d log OPT). We also prove a sharper instance-dependent recourse guarantee for the deterministic algorithm. For the vector bin packing problem, we make the so-called small jobs assumption that the size of all jobs in all the coordinates is O(1/log d) and present a simple O(1)-competitive algorithm with O(log n) recourse against oblivious adversaries. For both problems, the main challenge is to determine when and how to migrate jobs to maintain competitive solutions. Our central idea is that for each job, we make these decisions based only on the active set of jobs that are "earlier" than this job in some ordering ≺ of the jobs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • Vector Scheduling
  • Vector Load Balancing

Metrics

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

References

  1. B. Awerbuch, Y. Azar, E. Grove, M. Kao, P. Krishnan, and J. Vitter. Load balancing in the lp norm. In FOCS 1995, 1995. Google Scholar
  2. Baruch Awerbuch, Yossi Azar, Serge Plotkin, and Orli Waarts. Competitive routing of virtual circuits with unknown duration. J. Comput. Syst. Sci., 62(3):385-397, May 2001. URL: https://doi.org/10.1006/jcss.1999.1662.
  3. Yossi Azar, Ilan Reuven Cohen, Amos Fiat, and Alan Roytman. Packing small vectors. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 1511-1525, USA, 2016. Society for Industrial and Applied Mathematics. Google Scholar
  4. Yossi Azar, Ilan Reuven Cohen, Seny Kamara, and Bruce Shepherd. Tight bounds for online vector bin packing. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '13, pages 961-970, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2488608.2488730.
  5. Nikhil Bansal, Alberto Caprara, and Maxim Sviridenko. A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM J. Comput., 39(4):1256-1278, 2009. Google Scholar
  6. Nikhil Bansal, Marek Eliáš, and Arindam Khan. Improved approximation for vector bin packing. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 1561-1579, 2016. Google Scholar
  7. Niv Buchbinder, Yaron Fairstein, Konstantina Mellou, Ishai Menache, and Joseph (Seffi) Naor. Online virtual machine allocation with lifetime and load predictions. In Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '21, pages 9-10, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3410220.3456278.
  8. Chandra Chekuri and Sanjeev Khanna. On multidimensional packing problems. SIAM J. Comput., 33(4):837-851, 2004. Google Scholar
  9. Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Comput. Sci. Rev., 24:63-79, 2017. Google Scholar
  10. Edward G Coffman, Jr, Michael R Garey, and David S Johnson. Dynamic bin packing. SIAM Journal on Computing, 12(2):227-258, 1983. Google Scholar
  11. Graham Cormode and Pavel Veselý. Streaming algorithms for bin packing and vector scheduling. In Evripidis Bampis and Nicole Megow, editors, Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised Selected Papers, volume 11926 of Lecture Notes in Computer Science, pages 72-88. Springer, 2019. Google Scholar
  12. Wenceslas Fernandez de la Vega and George S. Lueker. Bin packing can be solved within 1+epsilon in linear time. Comb., 1(4):349-355, 1981. Google Scholar
  13. Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, and David Wajc. Fully-Dynamic Bin Packing with Little Repacking. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 51:1-51:24, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.51.
  14. M. R. Garey, Ronald L. Graham, David S. Johnson, and Andrew Chi-Chih Yao. Resource constrained scheduling as generalized bin packing. J. Comb. Theory, Ser. A, 21(3):257-298, 1976. Google Scholar
  15. David G. Harris and Aravind Srinivasan. The Moser-Tardos framework with partial resampling. J. ACM, 66(5):36:1-36:45, 2019. Google Scholar
  16. Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, and Debmalya Panigrahi. Tight bounds for online vector scheduling. SIAM J. Comput., 48(1):93-121, 2019. Google Scholar
  17. Adam Meyerson, Alan Roytman, and Brian Tagiku. Online multidimensional load balancing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 287-302, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  18. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Google Scholar
  19. Sai Sandeep. Almost optimal inapproximability of multidimensional packing problems. CoRR, abs/2101.02854, 2021. URL: http://arxiv.org/abs/2101.02854.
  20. Jeffery Westbrook. Load balancing for response time. In J. Algorithms, pages 355-368, 1994. 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