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 upper bound for maintaining (1+ϵ)-approximate single-source distances 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.

Dynamic algorithms for k-center on graphs

Cruciani, Emilio;
2024-01-01

Abstract

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 upper bound for maintaining (1+ϵ)-approximate single-source distances 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.
2024
978-1-61197-791-2
Approximation Algorithms; Location Problem; Clustering
File in questo prodotto:
File Dimensione Formato  
2024_35thACMSIAMSODA_3441_Cruciani.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 774.16 kB
Formato Adobe PDF
774.16 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/34724
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact