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