Approximate Dynamic Balanced Graph Partitioning

What is it about?

Networked systems today are becoming increasingly flexible, allowing resources like servers to be reconfigured based on the current traffic and demand. This flexibility can improve network performance, but frequent reconfigurations come with a cost. A major challenge is finding the right balance between improving efficiency and minimizing the overhead of these adjustments. In this paper, we revisit a problem known as dynamic balanced graph partitioning, where we are given a set of processes (tasks) that communicate with each other. These processes need to be assigned to a limited number of servers, and the way they are assigned impacts the communication cost. The key challenge is that we can change these assignments over time to improve performance, but each change comes at a cost. Previous work showed that in an online scenario, where communication patterns are unknown in advance, it is difficult to achieve optimal performance. Our focus, however, is on the offline version of the problem, where we know the entire communication sequence beforehand. We propose a new algorithm that provides a logarithmic approximation for solving this problem in polynomial time with some extra resources.

Featured Image