Dynamic Balanced Graph Partitioning
From MaRDI portal
Publication:5130579
DOI10.1137/17M1158513zbMath1465.68202arXiv1511.02074OpenAlexW3048797432MaRDI QIDQ5130579
Maciej Pacut, Andreas Loukas, Stefan Schmid, Chen Avin, Marcin Bienkowski
Publication date: 28 October 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.02074
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Competitive vertex recoloring. (Online disengagement), Improved analysis of online balanced clustering
Cites Work
- Unnamed Item
- Unnamed Item
- A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
- A strongly competitive randomized paging algorithm
- Balanced graph partitioning
- Competitive algorithms for distributed data management.
- Some simplified NP-complete graph problems
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Competitive randomized algorithms for nonuniform problems
- Competitive distributed file allocation.
- Competitive analysis of randomized paging algorithms
- Page replacement with multi-size pages and applications to web caching
- Online balanced repartitioning
- On-line generalized Steiner problem
- Competitive clustering of stochastic communication patterns on a ring
- Online file caching with rejection penalties
- Balanced partitions of trees and applications
- A Polylogarithmic Approximation of the Minimum Bisection
- Rent, Lease, or Buy: Randomized Algorithms for Multislope Ski Rental
- Divide-and-conquer approximation algorithms via spreading metrics
- On Variants of File Caching
- Approximating the minimum bisection size (extended abstract)
- Competitive paging algorithms
- Distributed Paging for General Networks
- Fast Approximate Graph Partitioning Algorithms
- Finding k Cuts within Twice the Optimal
- How Good is Recursive Bisection?
- Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration
- Online Network Design Algorithms via Hierarchical Decompositions
- A Polylogarithmic Approximation of the Minimum Bisection
- Expander flows, geometric embeddings and graph partitioning
- On page migration and other relaxed task systems
