Name
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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/978-3-030-92702-8_14 | WAOA |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcin Bienkowski | 1 | 0 | 1.01 |
| Martin Böhm | 2 | 3 | 1.77 |
| Martin Koutecký | 3 | 0 | 1.69 |
| Thomas Rothvoß | 4 | 0 | 0.34 |
| Jiří Sgall | 5 | 0 | 0.68 |
| Pavel Veselý | 6 | 0 | 1.69 |