Online load balancing with general reassignment cost

Berndt, S., Eberle, F. & Megow, N. (2022). Online load balancing with general reassignment cost. Operations Research Letters, 50(3), 322 - 328. https://doi.org/10.1016/j.orl.2022.03.007
Copy

We investigate a semi-online variant of load balancing with restricted assignment. In this problem, we are given n jobs, which need to be processed by m machines with the goal to minimize the maximum machine load. Since strong lower bounds rule out any competitive ratio of o(log⁡n), we may reassign jobs at a certain job-individual cost. We generalize a result by Gupta, Kumar, and Stein (SODA 2014) by giving a O(log⁡log⁡mn)-competitive algorithm with constant amortized reassignment cost.
Item Type Article
Copyright holders © 2022 The Authors
Departments LSE > Academic Departments > Mathematics
DOI 10.1016/j.orl.2022.03.007
Date Deposited 21 Apr 2022
Acceptance Date 29 Mar 2022
URI https://researchonline.lse.ac.uk/id/eprint/114914

Explore Further

picture_as_pdf
subject
Published Version
Creative Commons: Attribution-Noncommercial-No Derivative Works 4.0
Download

Export as

EndNote BibTeX Reference Manager Refer Atom Dublin Core JSON Multiline CSV
Export

Downloads
View more statistics