Online load balancing with general reassignment cost
Sebastian Berndt, Franziska Carola Eberle, Nicole Megow · Operations Research Letters · 2022
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(logn), 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(loglogmn)-competitive algorithm with constant amortized reassignment cost.