Dynamic balanced graph partitioning
From MaRDI portal
Abstract: This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between nodes, with patterns that may change over time, the objective is to service these requests efficiently by partitioning the nodes into clusters, each of size , such that frequently communicating nodes are located in the same cluster. The partitioning can be updated dynamically by migrating nodes between clusters. The goal is to devise online algorithms which jointly minimize the amount of inter-cluster communication and migration cost. The problem features interesting connections to other well-known online problems. For example, scenarios with generalize online paging, and scenarios with constitute a novel online variant of maximum matching. We present several lower bounds and algorithms for settings both with and without cluster-size augmentation. In particular, we prove that any deterministic online algorithm has a competitive ratio of at least , even with significant augmentation. Our main algorithmic contributions are an -competitive deterministic algorithm for the general setting with constant augmentation, and a constant competitive algorithm for the maximum matching variant.
Recommendations
Cites work
- A polylogarithmic approximation of the minimum bisection
- A Polylogarithmic Approximation of the Minimum Bisection
- A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
- A strongly competitive randomized paging algorithm
- Approximating the minimum bisection size (extended abstract)
- Balanced graph partitioning
- Balanced partitions of trees and applications
- Competitive algorithms for distributed data management.
- Competitive analysis of randomized paging algorithms
- Competitive clustering of stochastic communication patterns on a ring
- Competitive distributed file allocation.
- Competitive paging algorithms
- Competitive randomized algorithms for nonuniform problems
- Distributed Paging for General Networks
- Divide-and-conquer approximation algorithms via spreading metrics
- Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration
- Expander flows, geometric embeddings and graph partitioning
- Fast Approximate Graph Partitioning Algorithms
- Finding k Cuts within Twice the Optimal
- How Good is Recursive Bisection?
- scientific article; zbMATH DE number 5485537 (Why is no real title available?)
- On page migration and other relaxed task systems
- On variants of file caching
- On-line generalized Steiner problem
- Online balanced repartitioning
- Online file caching with rejection penalties
- Online network design algorithms via hierarchical decompositions
- Page replacement with multi-size pages and applications to web caching
- Partitioning graphs into balanced components
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Rent, lease, or buy: randomized algorithms for multislope ski rental
- Some simplified NP-complete graph problems
Cited in
(16)- Online balanced repartitioning
- Improved analysis of online balanced clustering
- Competitive clustering of stochastic communication patterns on a ring
- Online clique clustering
- Partitions of networks that are robust to vertex permutation dynamics
- Employee workload balancing by graph partitioning
- scientific article; zbMATH DE number 1617249 (Why is no real title available?)
- Competitive strategies for online clique clustering
- Streaming balanced graph partitioning algorithms for random graphs
- Competitive vertex recoloring. (Online disengagement)
- Efficient game theoretic approach to dynamic graph partitioning
- An improved approximation algorithm for dynamic minimum linear arrangement
- A subquadratic bound for online bisection
- Improved bounds for online balanced graph re-partitioning
- Simple dynamic spanners with near-optimal recourse against an adaptive adversary
- Competitive capacitated online recoloring
This page was built for publication: Dynamic balanced graph partitioning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5130579)
