Document Open Access Logo

Online Two-Dimensional Load Balancing

Authors Ilan Cohen, Sungjin Im, Debmalya Panigrahi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.34.pdf
  • Filesize: 0.58 MB
  • 21 pages

Document Identifiers

Author Details

Ilan Cohen
  • Jether Energy Ltd, Tel Aviv, Israel
Sungjin Im
  • Department of Computer Science and Engineering, University of California Merced, CA, USA
Debmalya Panigrahi
  • Department of Computer Science, Duke University, Durham, NC, USA

Funding

  • Im, Sungjin: Supported in part by NSF grants CCF-1409130, CCF-1617653, and CCF-1844939.
  • Panigrahi, Debmalya: Supported in part by NSF grants CCF-1535972, CCF-1955703, an NSF CAREER Award CCF-1750140, and the Indo-US Virtual Networked Joint Center on Algorithms under Uncertainty.

Cite AsGet BibTex

Ilan Cohen, Sungjin Im, and Debmalya Panigrahi. Online Two-Dimensional Load Balancing. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.34

Abstract

In this paper, we consider the problem of assigning 2-dimensional vector jobs to identical machines online so to minimize the maximum load on any dimension of any machine. For arbitrary number of dimensions d, this problem is known as vector scheduling, and recent research has established the optimal competitive ratio as O((log d)/(log log d)) (Im et al. FOCS 2015, Azar et al. SODA 2018). But, these results do not shed light on the situation for small number of dimensions, particularly for d = 2 which is of practical interest. In this case, a trivial analysis shows that the classic list scheduling greedy algorithm has a competitive ratio of 3. We show the following improvements over this baseline in this paper: - We give an improved, and tight, analysis of the list scheduling algorithm establishing a competitive ratio of 8/3 for two dimensions. - If the value of opt is known, we improve the competitive ratio to 9/4 using a variant of the classic best fit algorithm for two dimensions. - For any fixed number of dimensions, we design an algorithm that is provably the best possible against a fractional optimum solution. This algorithm provides a proof of concept that we can simulate the optimal algorithm online up to the integrality gap of the natural LP relaxation of the problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online algorithms
  • scheduling
  • multi-dimensional

Metrics

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

References

  1. Susanne Albers. Better bounds for online scheduling. SIAM J. Comput., 29(2):459-473, 1999. Google Scholar
  2. Susanne Albers. On randomized online scheduling. In STOC, pages 134-143, 2002. Google Scholar
  3. Susanne Albers. Online algorithms: a survey. Math. Program., 97(1-2):3-26, 2003. URL: https://doi.org/10.1007/s10107-003-0436-0.
  4. Susanne Albers and Matthias Hellwig. Semi-online scheduling revisited. Theor. Comput. Sci., 443:1-9, 2012. Google Scholar
  5. Yossi Azar. On-line load balancing. In Online Algorithms, The State of the Art., pages 178-195, 1996. Google Scholar
  6. 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 2016, Arlington, VA, USA, January 10-12, 2016, pages 1511-1525, 2016. Google Scholar
  7. Yossi Azar, Ilan Reuven Cohen, Seny Kamara, and F. Bruce Shepherd. Tight bounds for online vector bin packing. In Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, June 1-4, 2013, pages 961-970, 2013. Google Scholar
  8. Yossi Azar, Ilan Reuven Cohen, and Debmalya Panigrahi. Randomized algorithms for online vector load balancing. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 980-991, 2018. Google Scholar
  9. Yossi Azar and Oded Regev. On-line bin-stretching. Theor. Comput. Sci., 268(1):17-41, 2001. Google Scholar
  10. Yair Bartal, Amos Fiat, Howard J. Karloff, and Rakesh Vohra. New algorithms for an ancient scheduling problem. J. Comput. Syst. Sci., 51(3):359-366, 1995. Google Scholar
  11. Yair Bartal, Howard J. Karloff, and Yuval Rabani. A better lower bound for on-line scheduling. Inf. Process. Lett., 50(3):113-116, 1994. Google Scholar
  12. Martin Böhm, Jiří Sgall, Rob van Stee, and Pavel Veselý. A two-phase algorithm for bin stretching with stretching factor 1.5. J. Comb. Optim., 34(3):810-828, 2017. Google Scholar
  13. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, USA, 1998. Google Scholar
  14. Allan Borodin, Morten N Nielsen, and Charles Rackoff. (incremental) priority algorithms. Algorithmica, 37(4):295-326, 2003. Google Scholar
  15. Chandra Chekuri and Sanjeev Khanna. On multidimensional packing problems. SIAM J. Comput., 33(4):837-851, 2004. Google Scholar
  16. Edward Grady Coffman Jr, Michael Randolph Garey, and David Stifler Johnson. Approximation algorithms for bin packing: A survey. Approximation algorithms for NP-hard problems, pages 46-93, 1996. Google Scholar
  17. Richard Cole, Vasilis Gkatzelis, and Gagan Goel. Mechanism design for fair division: allocating divisible items without payments. In ACM Conference on Electronic Commerce, EC '13, Philadelphia, PA, USA, June 16-20, 2013, pages 251-268, 2013. Google Scholar
  18. Ulrich Faigle, Walter Kern, and György Turán. On the performance of on-line algorithms for partition problems. Acta Cybern., 9(2):107-119, 1989. Google Scholar
  19. Rudolf Fleischer and Michaela Wahl. Online scheduling revisited. In Algorithms - ESA 2000, 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000, pages 202-210, 2000. Google Scholar
  20. Michaël Gabay, Nadia Brauner, and Vladimir Kotov. Improved lower bounds for the online bin stretching problem. 4OR, 15(2):183-199, 2017. Google Scholar
  21. Michaël Gabay, Vladimir Kotov, and Nadia Brauner. Online bin stretching with bunch techniques. Theor. Comput. Sci., 602:103-113, 2015. Google Scholar
  22. Gábor Galambos and Gerhard J. Woeginger. An on-line scheduling heuristic with better worst case ratio than graham’s list scheduling. SIAM J. Comput., 22(2):349-355, 1993. Google Scholar
  23. M. R. Garey, Ronald L. Graham, David S. Johnson, and Andrew C. Yao. Resource constrained scheduling as generalized bin packing. J. Comb. Theory, Ser. A, 21(3):257-298, 1976. Google Scholar
  24. Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In Proc. 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2011. Google Scholar
  25. Todd Gormley, Nick Reingold, Eric Torng, and Jeffery Westbrook. Generating adversaries for request-answer games. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000, January 9-11, 2000, San Francisco, CA, USA., pages 564-565, 2000. Google Scholar
  26. R. L. Graham. Bounds for certain multiprocessing anomalies. Siam Journal on Applied Mathematics, 1966. Google Scholar
  27. R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17:416-429, 1969. Google Scholar
  28. J. F. Rudin III. Improved bound for the on-line scheduling problem. PhD thesis, The University of Texas at Dallas, 2001. Google Scholar
  29. Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, and Debmalya Panigrahi. Tight bounds for online vector scheduling. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 525-544, 2015. Google Scholar
  30. Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, and Maryam Shadloo. Online load balancing on related machines. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 30-43, 2018. Google Scholar
  31. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. In Proc. 46th ACM Symposium. on Theory of Computing (STOC), pages 313-322, 2014. Google Scholar
  32. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive flow time algorithms for polyhedral scheduling. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 506-524, 2015. Google Scholar
  33. David S Johnson. Near-optimal bin packing algorithms. PhD thesis, Massachusetts Institute of Technology, 1973. Google Scholar
  34. David S. Johnson. Fast algorithms for bin packing. J. Comput. Syst. Sci., 8(3):272-314, 1974. Google Scholar
  35. David S. Johnson, Alan Demers, Jeffrey D. Ullman, Michael R Garey, and Ronald L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on computing, 3(4):299-325, 1974. Google Scholar
  36. David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, and Ronald L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput., 3(4):299-325, 1974. Google Scholar
  37. David R. Karger, Steven J. Phillips, and Eric Torng. A better algorithm for an ancient scheduling problem. J. Algorithms, 20(2):400-430, 1996. Google Scholar
  38. Hans Kellerer and Vladimir Kotov. An efficient algorithm for bin stretching. Oper. Res. Lett., 41(4):343-346, 2013. Google Scholar
  39. Hans Kellerer, Vladimir Kotov, and Michaël Gabay. An efficient algorithm for semi-online multiprocessor scheduling with given total processing time. J. Scheduling, 18(6):623-630, 2015. Google Scholar
  40. Hans Kellerer, Vladimir Kotov, Maria Grazia Speranza, and Zsolt Tuza. Semi on-line algorithms for the partition problem. Oper. Res. Lett., 21(5):235-242, 1997. Google Scholar
  41. Gunho Lee, Byung-Gon Chun, and Randy H Katz. Heterogeneity-aware resource allocation and scheduling in the cloud. In Proceedings of the 3rd USENIX Workshop on Hot Topics in Cloud Computing, HotCloud, volume 11, 2011. Google Scholar
  42. Elisabeth Lübbecke, Olaf Maurer, Nicole Megow, and Andreas Wiese. A new approach to online scheduling: Approximating the optimal competitive ratio. ACM Trans. Algorithms, 13(1):15:1-15:34, 2016. URL: https://doi.org/10.1145/2996800.
  43. Adam Meyerson, Alan Roytman, and Brian Tagiku. Online multidimensional load balancing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013., pages 287-302, 2013. Google Scholar
  44. Lucian Popa, Gautam Kumar, Mosharaf Chowdhury, Arvind Krishnamurthy, Sylvia Ratnasamy, and Ion Stoica. Faircloud: sharing the network in cloud computing. In ACM SIGCOMM, pages 187-198. ACM, 2012. Google Scholar
  45. Kirk Pruhs, Jiří Sgall, and Eric Torng. Online scheduling. Handbook of scheduling: algorithms, models, and performance analysis, pages 15-1, 2004. Google Scholar
  46. Jiří Sgall. On-line scheduling. In Online Algorithms, pages 196-231, 1996. Google Scholar
  47. Jiří Sgall. Online scheduling. In Algorithms for Optimization with Incomplete Information, 16.-21. January 2005, 2005. Google Scholar
  48. Jiří Sgall. Online bin packing: Old algorithms and new results. In CiE, volume 8493 of Lecture Notes in Computer Science, pages 362-372. Springer, 2014. 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