Online load balancing with general reassignment cost

Berndt, Sebastian; Eberle, Franziska; and Megow, Nicole (2022) Online load balancing with general reassignment cost. Operations Research Letters, 50 (3). 322 - 328. ISSN 0167-6377

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
Keywords	competitive analysis,migration,online load balancing,recourse
Departments	Mathematics
DOI	10.1016/j.orl.2022.03.007
Date Deposited	21 Apr 2022 16:09
URI	https://researchonline.lse.ac.uk/id/eprint/114914

Explore Further

https://www.lse.ac.uk/Mathematics/people/Franziska-Eberle (Author)
10.1016/j.orl.2022.03.007 (DOI)

picture_as_pdf

picture_as_pdf
subject: Published Version
: Available under Creative Commons: Attribution-NonCommercial-No Derivative Works 4.0

Download

Atom

BibTeX

OpenURL ContextObject in Span

OpenURL ContextObject

Dublin Core

MPEG-21 DIDL

Data Cite XML

EndNote

HTML Citation

METS

MODS

RIOXX2 XML

Reference Manager

Refer

ASCII Citation

Export

Downloads