Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse

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. Along the way, we design an algorithm for the recourse version of the online generalized network flow problem (also known as network flow problem with gains). We have a graph with costs and capacities on the edges, and sources arrive online. Upon arrival of a source, we need to send unit flow from the source. In contrast to standard network flow, every edge uv in the network has a gain parameter-3uv > 0, meaning that θ-units of flow sent from u across uv becomes-3uv θ units of flow when it reaches v. In the recourse version, the algorithm can undo prior flow sent on an edge by incurring a linear cost. We present an online algorithm for the problem with recourse at most O(1/") times the offline optimum cost flow for the instance when edge capacities are scaled by a factor 1/1+". This marks an improvement over prior work in two ways: the known algorithms only apply to standard network flow (i.e., unit gains), and secondly, the guarantees held against an offline flow when edge capacities are scaled by a factor of (2+"). As an immediate corollary of this, we also obtain an improved algorithm for the online b-matching problem with reassignment costs.