2021/06/30 by Marcin Bienkowski, Martin Böhm, Bienkowski, Marcin +9
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.2107.00145
arxiv created 2021/08/24 · arxiv updated 2021/08/26
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.