Abstract
We study the online balanced graph repartitioning problem (OBGR) which was introduced by Avin, Bienkowski, Loukas, Pacut, and Schmid [Avin et al., 2020] and has recently received significant attention [Pacut et al., 2021; Henzinger et al., 2021; Henzinger et al., 2019; Tobias Forner et al., 2021; Bienkowski et al., 2021] owing to potential applications in largescale, dataintensive distributed computing. In OBGR, we have a set of 𝓁 clusters, each with k vertices (representing processes or virtual machines), and an online sequence of communication requests, each represented by a pair of vertices. Any request (u,v) incurs unit communication cost if u and v are located in different clusters (and zero otherwise). Any vertex can be migrated from one cluster to another at a migration cost of α ≥ 1. We consider the objective of minimizing the total communication and migration cost in the competitive analysis framework. The only known algorithms (which run in exponential time) include an O(k²𝓁²) competitive [Avin et al., 2020] and an O(k𝓁 2^O(k)) competitive algorithm [Bienkowski et al., 2021]. A lower bound of Ω(k𝓁) is known [Pacut et al., 2021]. In an effort to bridge the gap, recent results have considered beyond worst case analyses including resource augmentation (with augmented cluster capacity [Avin et al., 2020; Henzinger et al., 2019; Henzinger et al., 2021]) and restricted request sequences (the learning model [Henzinger et al., 2019; Henzinger et al., 2021; Pacut et al., 2021]).
In this paper, we give deterministic, polynomialtime algorithms for OBGR, which mildly exploit resource augmentation (i.e. augmented cluster capacity of (1+ε) k for arbitrary ε > 0). We improve beyond O(k²𝓁²)competitiveness (for general 𝓁, k) by first giving a simple algorithm with competitive ratio O(k𝓁²log k). Our main result is an algorithm with a significantly improved competitive ratio of O(k𝓁 log k). At a high level, we achieve this by employing i) an ILP framework to guide the allocation of large components, ii) a simple "any fit" style assignment of small components and iii) a charging argument which allows us to bound the cost of migrations. Like previous work on OBGR, our algorithm and analysis are phasebased, where each phase solves an independent instance of the learning model. Finally, we give an Ω(α k𝓁 log k) lower bound on the total cost incurred by any algorithm for OBGR under the learning model, which quantifies the limitation of a phasebased approach.
BibTeX  Entry
@InProceedings{rajaraman_et_al:LIPIcs.ESA.2022.83,
author = {Rajaraman, Rajmohan and Wasim, Omer},
title = {{Improved Bounds for Online Balanced Graph RePartitioning}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {83:183:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772471},
ISSN = {18688969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17021},
URN = {urn:nbn:de:0030drops170210},
doi = {10.4230/LIPIcs.ESA.2022.83},
annote = {Keywords: online algorithms, graph partitioning, competitive analysis}
}
Keywords: 

online algorithms, graph partitioning, competitive analysis 
Collection: 

30th Annual European Symposium on Algorithms (ESA 2022) 
Issue Date: 

2022 
Date of publication: 

01.09.2022 