Title:Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse

Abstract:We consider the online unrelated-machine load balancing problem with recourse, where the algorithm is allowed to re-assign prior jobs. We give a $(2+\epsilon)$-competitive algorithm for the problem with $O_\epsilon(\log n)$ amortized recourse per job. This is the first $O(1)$-competitive algorithm for the problem with reasonable recourse, and the competitive ratio nearly matches the long-standing best-known offline approximation guarantee. We also show an $O(\log\log n/\log\log\log n)$-competitive algorithm for the problem with $O(1)$ amortized recourse. The best-known bounds from prior work are $O(\log\log n)$-competitive algorithms with $O(1)$ amortized recourse due to [GKS14], for the special case of the restricted assignment model.
Along the way, we design an algorithm for the online generalized network flow problem (also known as network flow problem with gains) with recourse. In the problem, any edge $uv$ in the network has a gain parameter $\gamma_{uv} > 0$ and $\theta$-units of flow sent across $uv$ from $u$'s side becomes $\gamma_{uv} \theta$ units of flow on the $v$'th side. In the online problem, there is one sink, and sources come one by one. Upon arrival of a source, we need to send 1 unit flow from the source. A recourse occurs if we change the flow value of an edge. We give an online algorithm for the problem with recourse at most $O(1/\epsilon)$ times the optimum cost for the instance with capacities scaled by $\frac{1}{1+\epsilon}$. The $(1+\epsilon)$-factor improves upon the corresponding $(2+\epsilon)$-factor of [GKS14], which only works for the ordinary network flow problem. As an immediate corollary, we also give an improved algorithm for the online $b$-matching problem with reassignment costs.