Online Load Balancing with Recourse
Abstract:
We consider the online unrelated-machine load balancing problem with recourse. We have m machines, and jobs arrive online. Each job j, when assigned to machine i, increases the load of machine i by a value p_{i,j}. The goal is to assign jobs, immediately upon their arrival, to machines, to minimize the maximum load of any machine.
We take a new look at this classical problem in optimization, by allowing the algorithm to re-assign prior jobs, while keeping the number of such re-assignments (or recourse) small. We give a (2+ϵ)-competitive algorithm for the problem with logarithmic amortized recourse per job. This is the first O(1)-competitive algorithm for the problem with reasonable recourse, and moreover, the competitive ratio nearly matches the long-standing best-known approximation guarantee for even the offline version of the load balancing problem. The best-known bounds from prior work are O(loglogn)-competitive algorithms with O(1) amortized recourse due to [GKS14], for the special case of the restricted assignment model. Along the way, we design online algorithms for the so-called generalized network flow problem (also known as network flow problem with gains).
We take a new look at this classical problem in optimization, by allowing the algorithm to re-assign prior jobs, while keeping the number of such re-assignments (or recourse) small. We give a (2+ϵ)-competitive algorithm for the problem with logarithmic amortized recourse per job. This is the first O(1)-competitive algorithm for the problem with reasonable recourse, and moreover, the competitive ratio nearly matches the long-standing best-known approximation guarantee for even the offline version of the load balancing problem. The best-known bounds from prior work are O(loglogn)-competitive algorithms with O(1) amortized recourse due to [GKS14], for the special case of the restricted assignment model. Along the way, we design online algorithms for the so-called generalized network flow problem (also known as network flow problem with gains).
Speaker Bio
Ravishankar is a principal researcher at Microsoft Research India. He completed his PhD at Carnegie Mellon University in 2012. From 2012-2014, he was a Simons Postdoctoral Fellow at the CS Department in Princeton University. Long ago, he completed his BTech from IIT Madras in 2007. His research areas are broadly in algorithm design, especially in the online and stochastic optimization frameworks, with a focus on network design and clustering problems. He has also lately been working on designing fast, accurate and highly-scalable algorithms for the classical approximate nearest neighbor search (ANNS) problem and its numerous variants, with several applications in semantic search and information retrieval.