mlsanityData to 7 Oct 2026

Dynamic algorithms for k-center on graphs

arXiv 2307.15557 ↗First posted 28 Jul 2023cs.DS cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

21 of 44 references.

References · 21

  1. 2020Fully-Dynamic Coresetscited by 9
  2. 2018Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentiallycited by 8
  3. 2020Consistent k-Median: Simpler, Better and Robustcited by 7
  4. 2020Consistent k-Clustering for General Metricscited by 7
  5. 2015k-center Clustering under Perturbation Resiliencecited by 6
  6. 2023Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversariescited by 6
  7. 2019Fully Dynamic Maximal Independent Set with Polylogarithmic Update Timecited by 5
  8. 2023Fully Dynamic Consistent k-Center Clusteringcited by 5
  9. 2015Approximate Greedy Clustering and Distance Selection for Graph Metricscited by 3
  10. 2019Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Timecited by 3
  11. 2022Efficient and Stable Fully Dynamic Facility Locationcited by 3
  12. 2016Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphscited by 2
9 more
  1. 2017Dynamic clustering to minimize the sum of radiicited by 2
  2. 2019Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Timecited by 2
  3. 2021Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Timecited by 2
  4. 2021Fast Deterministic Fully Dynamic Distance Approximationcited by 2
  5. 2015Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Timecited by 1
  6. 2019A Tree Structure For Dynamic Facility Locationcited by 1
  7. 2020Near-Optimal Decremental Hopsets with Applicationscited by 1
  8. 2021Parameterized Approximation Algorithms for k-Center Clustering and Variantscited by 1
  9. 2023k-Center Clustering with Outliers in the MPC and Streaming Modelcited by 1

Built on by

Not cited yet.