---
OA_place: publisher
OA_type: gold
_id: '18308'
abstract:
- lang: eng
  text: We study in this paper the problem of maintaining a solution to k-median and
    k-means clustering in a fully dynamic setting. To do so, we present an algorithm
    to efficiently maintain a coreset, a compressed version of the dataset, that allows
    easy computation of a clustering solution at query time. Our coreset algorithm
    has near-optimal update time of Õ(k) in general metric spaces, which reduces to
    Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and
    O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means
    clustering in Euclidean space, this directly leads to an algorithm with update
    time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation,
    the query time is reduced to Õ(kd).
acknowledgement: "Monika Henzinger: This project has received funding from the European
  Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
  programme (MoDynStruct Grant agreement No. 101019564) and the Austrian Science Fund
  (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775
  with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nDavid Saulpic:
  Work partially done while at ISTA. Received funding from the European Union’s\r\nHorizon
  2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement
  No 101034413. This work was partially funded by the grant ANR-19-CE48-0016 from
  the French National Research Agency (ANR)."
alternative_title:
- LIPIcs
article_number: '100'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Max Dupré
  full_name: La Tour, Max Dupré
  last_name: La Tour
- 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: David
  full_name: Saulpic, David
  id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
  last_name: Saulpic
citation:
  ama: 'La Tour MD, Henzinger M, Saulpic D. Fully dynamic k-means coreset in near-optimal
    update time. In: <i>32nd Annual European Symposium on Algorithms</i>. Vol 308.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2024.100">10.4230/LIPIcs.ESA.2024.100</a>'
  apa: 'La Tour, M. D., Henzinger, M., &#38; Saulpic, D. (2024). Fully dynamic k-means
    coreset in near-optimal update time. In <i>32nd Annual European Symposium on Algorithms</i>
    (Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.ESA.2024.100">https://doi.org/10.4230/LIPIcs.ESA.2024.100</a>'
  chicago: La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Fully Dynamic
    K-Means Coreset in near-Optimal Update Time.” In <i>32nd Annual European Symposium
    on Algorithms</i>, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2024. <a href="https://doi.org/10.4230/LIPIcs.ESA.2024.100">https://doi.org/10.4230/LIPIcs.ESA.2024.100</a>.
  ieee: M. D. La Tour, M. Henzinger, and D. Saulpic, “Fully dynamic k-means coreset
    in near-optimal update time,” in <i>32nd Annual European Symposium on Algorithms</i>,
    London, United Kingdom, 2024, vol. 308.
  ista: 'La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in
    near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European
    Symposium on Algorithms, LIPIcs, vol. 308, 100.'
  mla: La Tour, Max Dupré, et al. “Fully Dynamic K-Means Coreset in near-Optimal Update
    Time.” <i>32nd Annual European Symposium on Algorithms</i>, vol. 308, 100, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2024.100">10.4230/LIPIcs.ESA.2024.100</a>.
  short: M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium
    on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
  end_date: 2024-09-04
  location: London, United Kingdom
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2024-09-02
corr_author: '1'
date_created: 2024-10-13T22:01:50Z
date_published: 2024-09-23T00:00:00Z
date_updated: 2025-12-02T13:49:11Z
day: '23'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2024.100
ec_funded: 1
external_id:
  arxiv:
  - '2406.19926'
  isi:
  - '001545622400100'
file:
- access_level: open_access
  checksum: 8e8c0b13049f11bb0133dfac22e32718
  content_type: application/pdf
  creator: dernst
  date_created: 2024-10-21T09:41:48Z
  date_updated: 2024-10-21T09:41:48Z
  file_id: '18454'
  file_name: 2024_LIPICs_DuprelaTour.pdf
  file_size: 873561
  relation: main_file
  success: 1
file_date_updated: 2024-10-21T09:41:48Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2024.100
has_accepted_license: '1'
intvolume: '       308'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
  grant_number: Z00422
  name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
  grant_number: P33775
  name: Fast Algorithms for a Reactive Network Layer
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: 32nd Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959773386'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic k-means coreset in near-optimal update time
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 308
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18309'
abstract:
- lang: eng
  text: 'The problem of designing connectivity oracles supporting vertex failures
    is one of the basic data structures problems for undirected graphs. It is already
    well understood: previous works [Duan-Pettie STOC''10; Long-Saranurak FOCS''22]
    achieve query time linear in the number of failed vertices, and it is conditionally
    optimal as long as we require preprocessing time polynomial in the size of the
    graph and update time polynomial in the number of failed vertices. We revisit
    this problem in the paradigm of algorithms with predictions: we ask if the query
    time can be improved if the set of failed vertices can be predicted beforehand
    up to a small number of errors. More specifically, we design a data structure
    that, given a graph G = (V,E) and a set of vertices predicted to fail D̂ ⊆ V of
    size d = |D̂|, preprocesses it in time Õ(d|E|) and then can receive an update
    given as the symmetric difference between the predicted and the actual set of
    failed vertices D̂△D = (D̂ ⧵ D) ∪ (D ⧵ D̂) of size η = |D̂△D|, process it in time
    Õ(η⁴), and after that answer connectivity queries in G ⧵ D in time O(η). Viewed
    from another perspective, our data structure provides an improvement over the
    state of the art for the fully dynamic subgraph connectivity problem in the sensitivity
    setting [Henzinger-Neumann ESA''16]. We argue that the preprocessing time and
    query time of our data structure are conditionally optimal under standard fine-grained
    complexity assumptions.'
acknowledgement: "Part of this work was done when Evangelos Kosinas was at University
  of Ioannina and Adam Polak was at Max Planck Institute of Informatics.\r\n"
alternative_title:
- LIPIcs
article_number: '72'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Bingbing
  full_name: Hu, Bingbing
  last_name: Hu
- first_name: Evangelos
  full_name: Kosinas, Evangelos
  id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949
  last_name: Kosinas
- first_name: Adam
  full_name: Polak, Adam
  last_name: Polak
citation:
  ama: 'Hu B, Kosinas E, Polak A. Connectivity oracles for predictable vertex failures.
    In: <i>32nd Annual European Symposium on Algorithms</i>. Vol 308. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2024. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2024.72">10.4230/LIPIcs.ESA.2024.72</a>'
  apa: 'Hu, B., Kosinas, E., &#38; Polak, A. (2024). Connectivity oracles for predictable
    vertex failures. In <i>32nd Annual European Symposium on Algorithms</i> (Vol.
    308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.ESA.2024.72">https://doi.org/10.4230/LIPIcs.ESA.2024.72</a>'
  chicago: Hu, Bingbing, Evangelos Kosinas, and Adam Polak. “Connectivity Oracles
    for Predictable Vertex Failures.” In <i>32nd Annual European Symposium on Algorithms</i>,
    Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href="https://doi.org/10.4230/LIPIcs.ESA.2024.72">https://doi.org/10.4230/LIPIcs.ESA.2024.72</a>.
  ieee: B. Hu, E. Kosinas, and A. Polak, “Connectivity oracles for predictable vertex
    failures,” in <i>32nd Annual European Symposium on Algorithms</i>, London, United
    Kingdom, 2024, vol. 308.
  ista: 'Hu B, Kosinas E, Polak A. 2024. Connectivity oracles for predictable vertex
    failures. 32nd Annual European Symposium on Algorithms. ESA: European Symposium
    on Algorithms, LIPIcs, vol. 308, 72.'
  mla: Hu, Bingbing, et al. “Connectivity Oracles for Predictable Vertex Failures.”
    <i>32nd Annual European Symposium on Algorithms</i>, vol. 308, 72, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2024, doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2024.72">10.4230/LIPIcs.ESA.2024.72</a>.
  short: B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
  end_date: 2024-09-04
  location: London, United Kingdom
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2024-09-02
corr_author: '1'
date_created: 2024-10-13T22:01:50Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-12-02T13:49:52Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2024.72
external_id:
  arxiv:
  - '2312.08489'
  isi:
  - '001545622400072'
file:
- access_level: open_access
  checksum: ab1f2f9161549a8763eda15db40e022c
  content_type: application/pdf
  creator: dernst
  date_created: 2024-10-21T10:03:48Z
  date_updated: 2024-10-21T10:03:48Z
  file_id: '18455'
  file_name: 2024_LIPICs_Hu.pdf
  file_size: 853914
  relation: main_file
  success: 1
file_date_updated: 2024-10-21T10:03:48Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2024.72
has_accepted_license: '1'
intvolume: '       308'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: 32nd Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959773386'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Connectivity oracles for predictable vertex failures
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 308
year: '2024'
...