Title: Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
| Speaker: | Shi Li |
| Affiliation: | University at Buffalo |
| Location: | MC 5501 |
Abstract: I will present the online algorithms for unrelated-machine load balancing problem with recourse. First, we shall present 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 shall also present 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 Gupta et al., 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 Gupta et al., 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.
This is based on joint work with Ravishankar Krishnaswamy and Varun Suriyanarayana. The paper will appear in STOC 2023.