Online load balancing with general reassignment cost

Authors:
  • SBSebastian Berndt
    Sebastian Berndt
  • FEFranziska Eberle
    Franziska Eberle
  • NMNicole Megow
    Nicole Megow

  • 1 January 2022
Abstract
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.
All Related Versions