**
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.