1. Improved Analysis of Online Balanced Clustering
- Author
-
Bienkowski, Marcin, Böhm, Martin, Koutecký, Martin, Rothvoß, Thomas, Sgall, Jiří, and Veselý, Pavel
- Subjects
FOS: Computer and information sciences ,Computer Science - Data Structures and Algorithms ,Data Structures and Algorithms (cs.DS) ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In the online balanced graph repartitioning problem, one has to maintain a clustering of $n$ nodes into $\ell$ clusters, each having $k = n / \ell$ nodes. During runtime, an online algorithm is given a stream of communication requests between pairs of nodes: an inter-cluster communication costs one unit, while the intra-cluster communication is free. An algorithm can change the clustering, paying unit cost for each moved node. This natural problem admits a simple $O(\ell^2 \cdot k^2)$-competitive algorithm COMP, whose performance is far apart from the best known lower bound of $\Omega(\ell \cdot k)$. One of open questions is whether the dependency on $\ell$ can be made linear; this question is of practical importance as in the typical datacenter application where virtual machines are clustered on physical servers, $\ell$ is of several orders of magnitude larger than $k$. We answer this question affirmatively, proving that a simple modification of COMP is $(\ell \cdot 2^{O(k)})$-competitive. On the technical level, we achieve our bound by translating the problem to a system of linear integer equations and using Graver bases to show the existence of a ``small'' solution.
- Published
- 2021
- Full Text
- View/download PDF