# Dynamic algorithms for k-center on graphs

arXiv: https://arxiv.org/abs/2307.15557 · HTML: https://mlsanity.com/paper/2307.15557/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 44 references that are in the map.
- First posted on arXiv 28 Jul 2023.

## Builds on (most cited first, 21 of 21)

- [Fully-Dynamic Coresets](https://mlsanity.com/paper/2004.14891/) (2020)
- [Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially](https://mlsanity.com/paper/1802.09205/) (2018)
- [Consistent k-Median: Simpler, Better and Robust](https://mlsanity.com/paper/2008.06101/) (2020)
- [Consistent k-Clustering for General Metrics](https://mlsanity.com/paper/2011.06888/) (2020)
- [k-center Clustering under Perturbation Resilience](https://mlsanity.com/paper/1505.03924/) (2015)
- [Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries](https://mlsanity.com/paper/2303.11843/) (2023)
- [Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time](https://mlsanity.com/paper/1909.03478/) (2019)
- [Fully Dynamic Consistent k-Center Clustering](https://mlsanity.com/paper/2307.13747/) (2023)
- [Approximate Greedy Clustering and Distance Selection for Graph Metrics](https://mlsanity.com/paper/1507.01555/) (2015)
- [Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time](https://mlsanity.com/paper/1909.03445/) (2019)
- [Efficient and Stable Fully Dynamic Facility Location](https://mlsanity.com/paper/2210.13880/) (2022)
- [Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs](https://mlsanity.com/paper/1605.02530/) (2016)
- [Dynamic clustering to minimize the sum of radii](https://mlsanity.com/paper/1707.02577/) (2017)
- [Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time](https://mlsanity.com/paper/1909.10850/) (2019)
- [Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2101.07149/) (2021)
- [Fast Deterministic Fully Dynamic Distance Approximation](https://mlsanity.com/paper/2111.03361/) (2021)
- [Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time](https://mlsanity.com/paper/1512.08148/) (2015)
- [A Tree Structure For Dynamic Facility Location](https://mlsanity.com/paper/1909.06653/) (2019)
- [Near-Optimal Decremental Hopsets with Applications](https://mlsanity.com/paper/2009.08416/) (2020)
- [Parameterized Approximation Algorithms for k-Center Clustering and Variants](https://mlsanity.com/paper/2112.10195/) (2021)
- [k-Center Clustering with Outliers in the MPC and Streaming Model](https://mlsanity.com/paper/2302.12811/) (2023)

## Abstract (arXiv)

In this paper we give the first efficient algorithms for the k-center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into k sets by choosing k centers such that the maximum distance from any data point to its closest center is minimized. It is known that it is NP-hard to get a better than 2 approximation for this problem. While in many applications the input may naturally be modeled as a graph, all prior works on k-center problem in dynamic settings are on point sets in arbitrary metric spaces. In this paper, we give a deterministic decremental (2+ε)-approximation algorithm and a randomized incremental (4+ε)-approximation algorithm, both with amortized update time kno(1) for weighted graphs. Moreover, we show a reduction that leads to a fully dynamic (2+ε)-approximation algorithm for the k-center problem, with worst-case update time that is within a factor k of the state-of-the-art fully dynamic (1+ε)-approximation single-source shortest paths algorithm in graphs. Matching this bound is a natural goalpost because the approximate distances of each vertex to its center can be used to maintain a (2+ε)-approximation of the graph diameter and the fastest known algorithms for such a diameter approximation also rely on maintaining approximate single-source distances.