  We consider the following online optimization problem. We are given a graph
$G$ and each vertex of the graph is assigned to one of $\ell$ servers, where
servers have capacity $k$ and we assume that the graph has $\ell \cdot k$
vertices. Initially, $G$ does not contain any edges and then the edges of $G$
are revealed one-by-one. The goal is to design an online algorithm
$\operatorname{ONL}$, which always places the connected components induced by
the revealed edges on the same server and never exceeds the server capacities
by more than $\varepsilon k$ for constant $\varepsilon>0$. Whenever
$\operatorname{ONL}$ learns about a new edge, the algorithm is allowed to move
vertices from one server to another. Its objective is to minimize the number of
vertex moves. More specifically, $\operatorname{ONL}$ should minimize the
competitive ratio: the total cost $\operatorname{ONL}$ incurs compared to an
optimal offline algorithm $\operatorname{OPT}$.
  Our main contribution is a polynomial-time randomized algorithm, that is
asymptotically optimal: we derive an upper bound of $O(\log \ell + \log k)$ on
its competitive ratio and show that no randomized online algorithm can achieve
a competitive ratio of less than $\Omega(\log \ell + \log k)$. We also settle
the open problem of the achievable competitive ratio by deterministic online
algorithms, by deriving a competitive ratio of $\Theta(\ell \lg k)$; to this
end, we present an improved lower bound as well as a deterministic
polynomial-time online algorithm.
  Our algorithms rely on a novel technique which combines efficient integer
programming with a combinatorial approach for maintaining ILP solutions. We
believe this technique is of independent interest and will find further
applications in the future.

Data Structures and Algorithms