---
_id: '11931'
abstract:
- lang: eng
  text: Clustering is one of the most fundamental problems in unsupervised learning
    with a large number of applications. However, classical clustering algorithms
    assume that the data is static, thus failing to capture many real-world applications
    where data is constantly changing and evolving. Driven by this, we study the metric
    k-center clustering problem in the fully dynamic setting, where the goal is to
    efficiently maintain a clustering while supporting an intermixed sequence of insertions
    and deletions of points. This model also supports queries of the form (1) report
    whether a given point is a center or (2) determine the cluster a point is assigned
    to. We present a deterministic dynamic algorithm for the k-center clustering problem
    that provably achieves a (2 + ∊)-approximation in nearly logarithmic update and
    query time, if the underlying metric has bounded doubling dimension, its aspect
    ratio is bounded by a polynomial and ∊ is a constant. An important feature of
    our algorithm is that the update and query times are independent of k. We confirm
    the practical relevance of this feature via an extensive experimental study which
    shows that for large values of k, our algorithmic construction outperforms the
    state-of-the-art algorithm in terms of solution quality and running time.
article_processing_charge: No
author:
- first_name: Gramoz
  full_name: Goranci, Gramoz
  last_name: Goranci
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Dariusz
  full_name: Leniowski, Dariusz
  last_name: Leniowski
- first_name: Christian
  full_name: Schulz, Christian
  last_name: Schulz
- first_name: Alexander
  full_name: Svozil, Alexander
  last_name: Svozil
citation:
  ama: 'Goranci G, Henzinger MH, Leniowski D, Schulz C, Svozil A. Fully dynamic k-center
    clustering in low dimensional metrics. In: <i>2021 Proceedings of the Workshop
    on Algorithm Engineering and Experiments</i>. Society for Industrial and Applied
    Mathematics; 2021:143-153. doi:<a href="https://doi.org/10.1137/1.9781611976472.11">10.1137/1.9781611976472.11</a>'
  apa: 'Goranci, G., Henzinger, M. H., Leniowski, D., Schulz, C., &#38; Svozil, A.
    (2021). Fully dynamic k-center clustering in low dimensional metrics. In <i>2021
    Proceedings of the Workshop on Algorithm Engineering and Experiments</i> (pp.
    143–153). Alexandria, VA, United States: Society for Industrial and Applied Mathematics.
    <a href="https://doi.org/10.1137/1.9781611976472.11">https://doi.org/10.1137/1.9781611976472.11</a>'
  chicago: Goranci, Gramoz, Monika H Henzinger, Dariusz Leniowski, Christian Schulz,
    and Alexander Svozil. “Fully Dynamic K-Center Clustering in Low Dimensional Metrics.”
    In <i>2021 Proceedings of the Workshop on Algorithm Engineering and Experiments</i>,
    143–53. Society for Industrial and Applied Mathematics, 2021. <a href="https://doi.org/10.1137/1.9781611976472.11">https://doi.org/10.1137/1.9781611976472.11</a>.
  ieee: G. Goranci, M. H. Henzinger, D. Leniowski, C. Schulz, and A. Svozil, “Fully
    dynamic k-center clustering in low dimensional metrics,” in <i>2021 Proceedings
    of the Workshop on Algorithm Engineering and Experiments</i>, Alexandria, VA,
    United States, 2021, pp. 143–153.
  ista: 'Goranci G, Henzinger MH, Leniowski D, Schulz C, Svozil A. 2021. Fully dynamic
    k-center clustering in low dimensional metrics. 2021 Proceedings of the Workshop
    on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering
    and Experiments, 143–153.'
  mla: Goranci, Gramoz, et al. “Fully Dynamic K-Center Clustering in Low Dimensional
    Metrics.” <i>2021 Proceedings of the Workshop on Algorithm Engineering and Experiments</i>,
    Society for Industrial and Applied Mathematics, 2021, pp. 143–53, doi:<a href="https://doi.org/10.1137/1.9781611976472.11">10.1137/1.9781611976472.11</a>.
  short: G. Goranci, M.H. Henzinger, D. Leniowski, C. Schulz, A. Svozil, in:, 2021
    Proceedings of the Workshop on Algorithm Engineering and Experiments, Society
    for Industrial and Applied Mathematics, 2021, pp. 143–153.
conference:
  end_date: 2021-01-11
  location: Alexandria, VA, United States
  name: 'ALENEX: Symposium on Algorithm Engineering and Experiments'
  start_date: 2021-01-10
date_created: 2022-08-19T07:33:37Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2023-02-17T13:58:51Z
day: '01'
doi: 10.1137/1.9781611976472.11
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1137/1.9781611976472.11
month: '01'
oa: 1
oa_version: Published Version
page: 143 -153
publication: 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments
publication_identifier:
  eisbn:
  - 978-1-61197-647-2
  issn:
  - 2164-0300
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic k-center clustering in low dimensional metrics
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...