Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
Ravishankar Krishnaswamy, Shi Li, Varun Suriyanarayana · 2023
We consider the recourse version of the classical online load balancing problem on unrelated machines, where the algorithm is allowed to re-assign prior jobs. We give a (2+є)-competitive algorithm for the problem with Oє(logn) amortized recourse per job. This is the first O(1)-competitive algorithm for the problem with non-trivial recourse, and the competitive ratio nearly matches the long-standing best-known offline approximation guarantee. We also show an O(loglogn/logloglogn)-competitive algorithm for the problem with O(1) amortized recourse. The best-known bounds from prior work are O(loglogn)-competitive algorithms with O(1) amortized recourse due to Gupta et al., for the special case of the restricted assignment model.