Dynamic algorithms for k-center on graphs Article Swipe

MAKE IMPACT

Emilio Cruciani , Sebastian Förster , Gramoz Goranci , Yasamin Nazari , Antonis Skarlatos · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2307.15557

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 $kn^{o(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.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2307.15557

PDF

https://arxiv.org/pdf/2307.15557

OA Status

green

Cited By

1

Related Works

10

OpenAlex ID

https://openalex.org/W4385437165

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4385437165

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2307.15557

Digital Object Identifier

Title

Dynamic algorithms for k-center on graphs

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-07-28

Full publication date if available

Authors

Emilio Cruciani, Sebastian Förster, Gramoz Goranci, Yasamin Nazari, Antonis Skarlatos

List of authors in order

Landing page

https://arxiv.org/abs/2307.15557

Publisher landing page

PDF URL

https://arxiv.org/pdf/2307.15557

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2307.15557

Direct OA link when available

Concepts

Approximation algorithm, Combinatorics, Center (category theory), Mathematics, Algorithm, Vertex (graph theory), Matching (statistics), Partition (number theory), Dynamic problem, Vertex cover, Discrete mathematics, Graph, Chemistry, Statistics, Crystallography

Top concepts (fields/topics) attached by OpenAlex

Cited by

1

Total citation count in OpenAlex

Citations by year (recent)

2025: 1

Per-year citation counts (last 5 years)

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload