Skip to main content

Online two-dimensional load balancing

Publication ,  Conference
Cohen, I; Im, S; Panigrahi, D
Published in: Leibniz International Proceedings in Informatics, LIPIcs
June 1, 2020

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( logloglogdd ) (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.

Duke Scholars

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783959771382

Publication Date

June 1, 2020

Volume

168

Related Subject Headings

  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Cohen, I., Im, S., & Panigrahi, D. (2020). Online two-dimensional load balancing. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 168). https://doi.org/10.4230/LIPIcs.ICALP.2020.34
Cohen, I., S. Im, and D. Panigrahi. “Online two-dimensional load balancing.” In Leibniz International Proceedings in Informatics, LIPIcs, Vol. 168, 2020. https://doi.org/10.4230/LIPIcs.ICALP.2020.34.
Cohen I, Im S, Panigrahi D. Online two-dimensional load balancing. In: Leibniz International Proceedings in Informatics, LIPIcs. 2020.
Cohen, I., et al. “Online two-dimensional load balancing.” Leibniz International Proceedings in Informatics, LIPIcs, vol. 168, 2020. Scopus, doi:10.4230/LIPIcs.ICALP.2020.34.
Cohen I, Im S, Panigrahi D. Online two-dimensional load balancing. Leibniz International Proceedings in Informatics, LIPIcs. 2020.

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783959771382

Publication Date

June 1, 2020

Volume

168

Related Subject Headings

  • 46 Information and computing sciences