TY - GEN

T1 - Approximate Dynamic Balanced Graph Partitioning

AU - Räcke, Harald

AU - Schmid, Stefan

AU - Zabrodin, Ruslan

N1 - Publisher Copyright:
© 2022 ACM.

PY - 2022/7/11

Y1 - 2022/7/11

N2 - Networked systems are increasingly flexible and reconfigurable. This enables demand-aware infrastructures whose resources can be adjusted according to the traffic pattern they currently serve. This paper revisits the dynamic balanced graph partitioning problem, a generalization of the classic balanced graph partitioning problem. We are given a set P of n = kl processes which communicate over time according to a given request sequence s. The processes are assigned to l servers (each of capacity k), and a scheduler can change this assignment dynamically to reduce communication costs, at cost a per node move. Avin et al. showed an O(k) lower bound on the competitive ratio of any deterministic online algorithm, even in a model with resource augmentation, and presented an O(k log k)-competitive online algorithm. We study the offline version of this problem where s is known to the algorithm. Our main contribution is a polynomial-time algorithm which provides an O(log n)-approximation with resource augmentation. Our algorithm relies on an integer linear program formulation in a metric space with spreading constraints. We relax the formulation to a linear program and employ Bartal's clustering algorithm in a novel way to round it.

AB - Networked systems are increasingly flexible and reconfigurable. This enables demand-aware infrastructures whose resources can be adjusted according to the traffic pattern they currently serve. This paper revisits the dynamic balanced graph partitioning problem, a generalization of the classic balanced graph partitioning problem. We are given a set P of n = kl processes which communicate over time according to a given request sequence s. The processes are assigned to l servers (each of capacity k), and a scheduler can change this assignment dynamically to reduce communication costs, at cost a per node move. Avin et al. showed an O(k) lower bound on the competitive ratio of any deterministic online algorithm, even in a model with resource augmentation, and presented an O(k log k)-competitive online algorithm. We study the offline version of this problem where s is known to the algorithm. Our main contribution is a polynomial-time algorithm which provides an O(log n)-approximation with resource augmentation. Our algorithm relies on an integer linear program formulation in a metric space with spreading constraints. We relax the formulation to a linear program and employ Bartal's clustering algorithm in a novel way to round it.

KW - approximation algorithms

KW - clustering

KW - graph partitioning

KW - lp rounding

UR - http://www.scopus.com/inward/record.url?scp=85134372734&partnerID=8YFLogxK

U2 - 10.1145/3490148.3538563

DO - 10.1145/3490148.3538563

M3 - Conference contribution

AN - SCOPUS:85134372734

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 401

EP - 409

BT - SPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

T2 - 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022

Y2 - 11 July 2022 through 14 July 2022

ER -