Abstract
In the online balanced graph repartitioning problem, one has to maintain a clustering of n nodes into ℓ clusters, each having k= n/ ℓ 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(ℓ2. k2) -competitive algorithm Comp, whose performance is far apart from the best known lower bound of Ω(ℓ. k).
One of open questions is whether the dependency on ℓ can be made linear; this question is of practical importance as in the typical datacenter application where virtual machines are clustered on physical servers, ℓ is of several orders of magnitude larger than k. We answer this question affirmatively, proving that a simple modification of Comp is (ℓ. 2O(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.