Fully Dynamic k-Center Clustering in Doubling Metrics

Alexander Svozil; Christian Schulz; Dariusz Leniowski; Gramoz Goranci; Monika Henzinger

REVIEW 3 major objections 4 minor 28 references

Fully Dynamic k-Center Clustering in Doubling Metrics

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves a deterministic fully dynamic (2+epsilon)-approximation for k-center clustering in doubling metrics whose per-update time is polylogarithmic in the aspect ratio and independent of k.

desk verdict First k-independent fully-dynamic k-center in doubling metrics, but the (2+ε) guarantee is unproved as written; a rescaling patch fixes it. read the letter →

arxiv 1908.03948 v3 pith:KOUPBEW5 submitted 2019-08-11 cs.DS

Gramoz Goranci , Monika Henzinger , Dariusz Leniowski , Christian Schulz , Alexander Svozil This is my paper · ORCID

classification cs.DS

keywords k-centerclusteringfullydynamicalgorithmdoublingdimensionnavigatingnetsr-netsaspectratiocovertreesqueries

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper gives a deterministic algorithm for maintaining a k-center clustering of a point set that is changing by insertions and deletions, and proves that in metrics with bounded doubling dimension the time per update is polylogarithmic in the aspect ratio and does not depend on k at all. The maintained clustering is always a (2+epsilon)-approximation of the optimal one, matching the approximation quality of the best known dynamic algorithms for general metrics but removing their k-dependence. A sympathetic reader should care because k is often large in applications such as server placement, and the k-dependence in previous fully dynamic algorithms was believed to be hard to remove. The paper backs the theoretical claim with an implementation using cover trees, reporting speedups over the previous state-of-the-art for large k and epsilon.

What carries the argument

The machinery is a family of navigating nets with shifted scales. A navigating net is a hierarchy of $r$-nets: for each scale $r$, a set $Y_r$ of points that are mutually at distance at least $r$ while every point of the next-finer net lies within $r$ of some $Y_r$ point; the hierarchy is maintained under insertions and deletions by a dynamic data structure whose per-update work is $2^{O(\kappa)} \log \Delta \log\log\Delta$. The paper runs $m$ copies of this hierarchy in parallel, each with radius set $\{\alpha^{i+(p/m)-1}\}$, and for each net locates the scale $\alpha^{i^*}$ whose level has at most $k$ points while the next coarser level has more than $k$. The shift between the $m$ nets guarantees that the optimal cost falls within one of the gaps, so the best of the $m$ candidate radii is within $(2+\epsilon)$ of OPT. This machinery replaces the $O(k)$ work of examining centers with $O(1)$ counter checks per level and a min-heap lookup for cluster queries.

What would settle it

Run an adversarial sequence that repeatedly inserts and deletes points near the same location in a doubling metric of constant dimension and, at every update, count the total number of navigation-list changes across all levels and all m nets. If any single update causes more than O($2^{{O(kappa)}}$ log $\Delta$ log log $\Delta$) changes, or if the maintained hierarchy ever violates the invariant that same-level points are at distance at least r while every point of the finer level is within r of a same-level point, then the claimed k-independent polylog update time is falsified.

Watch

Extended reading notes

Core claim

The central claim is that a (2+epsilon)-approximate solution to the fully dynamic k-center problem can be maintained in $O(2^{O(\kappa)} \log \Delta \log\log\Delta \cdot \epsilon^{-1}\ln\epsilon^{-1})$ update time and $O(1)$ or $O(\log \Delta)$ query time, where $\kappa$ is the doubling dimension and $\Delta$ the aspect ratio. The key is to maintain, not one hierarchy of $r$-nets, but $m = O(\epsilon^{-1}\ln\epsilon^{-1})$ navigating nets whose radius scales are shifted by fractional powers of $\alpha$. At every scale the data structure reports how many points occupy the net; the algorithm picks the net with the smallest radius whose count is at most $k$, and its points are the centers. A geometric-series argument shows every point is within radius $\frac{\alpha}{\alpha-1}\alpha^{i^*}$ of a center, while a packing argument shows that radius is at most $(2+\epsilon)$ times the optimum. The update and query cost is independent of $k$ because the navigating nets are maintained without ever enumerating or iterating over the current center set.

Load-bearing premise

The whole running-time promise rests on the dynamic navigating-net data structure actually supporting point deletions in O($2^{{O(kappa)}}$ log $\Delta$ log log $\Delta$) time while preserving its covering and separation invariants at every scale; if deletions require more work or disturb more of the hierarchy, the update time is no longer independent of k.

Editorial extensions

If this is right

In any metric of bounded doubling dimension, k-center clustering can be maintained at the (2+epsilon) approximation frontier with update time independent of the number of centers.
Queries asking whether a point is a center cost O(1) and queries asking which cluster contains a point cost O(log Delta), so the structure can be used inside larger dynamic pipelines that need membership lookups.
The algorithm is deterministic, so its guarantees hold against adaptive adversarial update sequences, unlike the earlier randomized general-metric algorithm.
For constant epsilon and polynomially bounded aspect ratio, the update time becomes polylogarithmic in the number of points, giving essentially O(polylog n) per insertion or deletion.
When k and epsilon are moderately large, the cover-tree implementation is faster and gives lower-cost solutions than the previous fully dynamic baseline.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the update time is independent of k, the same data structure could serve as a black box for dynamic variants where k itself changes over time, with the current k read directly from the maintained level counters.
The shift-and-pick scheme for multiple nets is a general decoupling technique: a similar construction might apply to other hierarchical clustering objectives in doubling metrics, such as sum-of-radii or k-median, wherever a hierarchy of nets can be maintained dynamically.
The experiments replace navigating nets with cover trees, which store only one parent per point per level; if cover trees can be shown to support deletions with the same per-update bound, the theoretical guarantee would survive without the heavier navigating-net machinery.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things before you read. The paper delivers a genuinely new result: a deterministic fully-dynamic k-center algorithm for bounded doubling metrics with update time O(2^{O(κ)} log Δ log log Δ · ε^{-1} ln ε^{-1}), independent of k. That answers the open question that Chan et al. left. Second, as written, Theorem 1.1 is not proved: Lemma 3.2's own derivation gives a 2(1+ε)^2 bound, and the stated choice of m is not enough even to force α^{1/m} ≤ 1+ε. The gap is patchable by rescaling ε, but it is real and the paper should be corrected.

What is actually new: the combination of Krauthgamer-Lee navigating nets with McCutchen-Khuller's scaled hierarchy is natural but non-obvious, and the k-independent update time is the right headline. The deterministic guarantee is a clear step over prior randomized or k-dependent bounds. I found the data-structure section detailed enough to check the main accounting, and the experimental study is honest and useful: it directly tests the k-dependence and shows large speedups when k and ε are in the regime the theory points to.

Where it is soft. First, Lemma 3.2. The algebra gives cost_{p*}/OPT ≤ 2α/(α−1) α^{1/m}. With α=2/ε that is 2(1+ε)^2, not 2+ε. The asserted threshold m ≥ ε^{-1}ln2 + ε^{-1}lnε^{-1} does not imply α^{1/m} ≤ 1+ε because ln(1+ε) is smaller than ε. Both issues are fixed by running the scheme with ε' ≈ ε/4; the O(ε^{-1}lnε^{-1}) time is unchanged in asymptotic form. But the theorem, as written, claims more than the proof shows. Second, the k-independent update time leans entirely on [22, Thm 2.5] for deletions in navigating nets. That is a black box; the paper should make explicit what [22] proves, including deletion cost, and why it applies unchanged here. If that theorem doesn't deliver deletions at that cost, the headline breaks. This is a reliance, not a demonstrated error. Third, the ACov cover-tree version is asserted to inherit the (2+ε) guarantee without a supporting argument. I'd want at least a lemma or a citation showing the cover tree levels are nets in the required sense before I'd quote the experiments as a validation of the theory.

Overall, the central algorithm is plausible and the stated flaws are correctable. I'd take this seriously in peer review; it belongs at a strong algorithms venue and should come back with the scaling fixed and the [22] dependence spelled out. Worth bringing to a reading group, and I'd cite it once the bound is restated.

Referee Report

3 major / 4 minor

Summary. The paper studies the fully dynamic k-center clustering problem in metric spaces of bounded doubling dimension. The main theoretical contribution is a deterministic data structure that, according to Theorem 1.1, maintains a (2+epsilon)-approximate k-center solution under point insertions and deletions in O(2^{O(kappa)} log Delta log log Delta * epsilon^{-1} ln epsilon^{-1}) time per update, independent of k, with O(1) center-membership queries and O(log Delta) cluster-assignment queries. The construction maintains m = O(epsilon^{-1} ln epsilon^{-1}) navigating nets with interleaved geometric scale sets, chooses the net whose associated cost is minimal, and uses the appropriate level of that net as the current k-center solution. The proof of the approximation guarantee appears in Lemmas 3.1 and 3.2. The paper also reports an experimental comparison of a cover-tree variant against the algorithm of Chan et al., measuring speedup and solution quality over several datasets and update sequences.

Significance. If the identified gaps are repaired, this would be a strong and well-motivated result: a deterministic fully dynamic k-center algorithm with update time independent of k in doubling metrics, matching the static 2-approximation up to an additive epsilon. The interleaved-net idea is natural, and the claimed k-independence is a genuine improvement over prior dynamic algorithms whose update time depends polynomially on k. The paper also provides an experimental study with a public source code link and gives useful empirical evidence for the practical relevance of the k-independent bound, although the experiments use cover trees rather than navigating nets. The central proof is not machine-checked, but the structure of the argument is clear and the main gaps appear local and patchable rather than fatal. For these reasons the paper deserves a major revision rather than rejection.

major comments (3)

[Lemma 3.2] The final inequality chain in Lemma 3.2 does not prove the stated (2+epsilon) ratio. The proof establishes cost_{p*}/OPT <= 2(1+epsilon)^2, which equals 2+4epsilon+2epsilon^2, not 2+epsilon. Moreover, the condition m >= epsilon^{-1} ln 2 + epsilon^{-1} ln epsilon^{-1} is insufficient to force alpha^{1/m} <= 1+epsilon with alpha = 2/epsilon: the correct requirement is m >= ln(2/epsilon)/ln(1+epsilon), which is strictly larger because ln(1+epsilon) < epsilon. Thus, as written, Lemma 3.2 does not support the approximation guarantee in Theorem 1.1. This is fixable by choosing m >= ln(2/epsilon)/ln(1+epsilon), which still gives m = O(epsilon^{-1} ln epsilon^{-1}), or by rescaling epsilon, but the lemma and the theorem statement need to be corrected and reproved.
[Section 3.2] The claimed k-independent update time rests entirely on [22, Theorem 2.5] as a black box for deletions in navigating nets. The paper does not state the exact theorem or explain why it maintains, for every scale, the r-net covering and separation invariants that Lemma 3.1 and Lemma 3.2 require. In particular, Lemma 3.1 uses the exact covering radius alpha^i, while the data-structure description uses navigation lists of radius psi*alpha^i with psi >= 4. If the cited data structure guarantees only a covering radius larger than alpha^i, the approximation constant becomes 2psi+O(epsilon) rather than 2+O(epsilon). The authors should quote the precise invariant maintained by [22] and prove that it matches the r-net definitions used in the approximation analysis.
[Lemma 3.2] The step 'Consequently, |Y^{p-hat}_{alpha-hat}| > k >= |Y^{p*}_{alpha^{i*}}|' is not immediate, because alpha-hat is the previous scale in the global interleaved sequence and belongs to a different navigating net than p*. The claim follows only after using the minimality of p*: if |Y^{p-hat}_{alpha-hat}| <= k, then the threshold exponent for net p-hat would be at most the exponent of alpha-hat, giving cost_{p-hat} < cost_{p*}, a contradiction. This argument should be stated explicitly, since the current proof leaves a logical gap in a load-bearing step.

minor comments (4)

[Section 3.1, definition of i*] The notation 'Y^p_{alpha^{i*}-1}' is ambiguous: it should be written as Y^p_{alpha^{i*-1}} or explained explicitly as the previous scale in the same net.
[Throughout] The paper sometimes uses 'k-center solution' when the chosen net can have fewer than k centers; since adding arbitrary points to the center set only decreases the cost, the approximation guarantee is unaffected, but this padding step should be mentioned.
[Section 4] The experimental section claims that the cover-tree variant yields the same (2+epsilon) guarantee as the navigating-net construction, but the invariants of cover trees are only informally stated; a precise statement of the maintained invariants would make the empirical bridge to the theory more convincing.
[References] Reference [22] is cited by theorem number in the text, but the bibliographic entry gives only the paper title and venue. Adding the theorem or chapter of the statement used would help readers verify the black-box assumption.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the approximation analysis is self-contained given the external navigating-net data structure and the independent scaling argument.

full rationale

The paper's central derivation does not reduce to its own inputs. In Section 3.1, the algorithm maintains m navigating nets with differing base distances, where the r-net separation and covering invariants are imported from the external published work of Krauthgamer and Lee [22], not from the present authors' previous results. Lemma 3.1 bounds the distance from any point to the selected center set by a geometric series using the covering property, and Lemma 3.2 compares the chosen net level against the optimum via the triangle inequality and the separation property; the ratio cost_p*/OPT is bounded as 2α/(α-1) · α^{1/m}, and no parameter is fitted to the target approximation or to any data. The k-independent update time in Section 3.2 rests on Theorem 2.5 of [22], which is an independent, external data-structure claim, not a self-citation. The only self-citations in the paper, [8], [13], and [17], appear in the related-work discussion and are not load-bearing for Theorem 1.1. The experimental section compares an implementation against the external algorithm of Chan et al. [2] and does not define its success criterion in terms of the paper's own fitted values. The skeptical observation that Lemma 3.2 proves only a (2+O(epsilon)) bound with the stated parameter choice is a genuine technical correctness gap, but it is an algebra error in an otherwise independent argument, not a circularity: the claimed (2+epsilon) guarantee is not assumed as an input anywhere in the derivation. Therefore, no step of the derivation is equivalent to its inputs by construction, and the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on an external data structure, the doubling/aspect-ratio assumptions, and standard r-net properties. There are no fitted parameters and no newly postulated entities. The main proof gap is the constant accounting in Lemma 3.2.

assumptions (3)

domain assumption The Krauthgamer-Lee navigating net data structure supports point insertions and deletions in doubling metrics with update time O(2^{O(κ)} log Δ log log Δ) while preserving r-net invariants.
Invoked in Section 3.2 as Theorem 2.5 and Chapters 2.5-2.6 of [22]. If false, the central k-independent update time guarantee collapses.
domain assumption The underlying metric has bounded doubling dimension κ with constant κ and aspect ratio Δ = dmax/dmin polynomial in the input size.
Stated in Theorem 1.1; needed for the polylogarithmic update time and the O(log Δ) query time.
standard math Standard properties of r-nets: separating points are at distance at least r, and each point is covered within radius r.
Used in the proofs of Lemmas 3.1 and 3.2, and in the definition of navigating nets in Section 3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Fully Dynamic k-Center Clustering in Doubling Metrics." pith.science (2026). https://pith.science/paper/KOUPBEW5

@misc{pith2026190803948,
  author       = {Pith},
  title        = {Pith review of: Fully Dynamic k-Center Clustering in Doubling Metrics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KOUPBEW5}},
  note         = {Machine review of arXiv:1908.03948}
}

abstract

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+\epsilon)$-approximation in poly-logarithmic update and query time, if the underlying metric has bounded doubling dimension, its aspect ratio is bounded by a polynomial and $\epsilon$ 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 values of $k$ and $\epsilon$ suggested by theory, our algorithmic construction outperforms the state-of-the-art algorithm in terms of solution quality and running time.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 24 canonical work pages

[22]

Robert Krauthgamer and James R. Lee. Navigating nets: si mple algorithms for proximity search. In Symposium on Discrete Algorithms (SODA) , pages 798–807, 2004

work page 2004
[1]

Beygelzimer, S

A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for ne arest neighbor. In ICML. ACM, 2006

work page 2006
[2]

Hubert Chan, Arnaud Guerqin, and Mauro Sozio

T.-H. Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dyn amic k-center clustering. In Inter- national World Wide Web Conference (WWW) , pages 579–587, 2018

work page 2018
[3]

Hubert Chan, Arnaud Guerqin, and Mauro Sozio

T.-H. Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dyn amic k-center clustering GitHub Repository. https://github.com/fe6Bc5R4JvLkFkSeExHM/k-center, 2018

work page 2018
[4]

Incremental clustering and dynamic information retrieval

Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev M otwani. Incremental clustering and dynamic information retrieval. SIAM J. Comput. , 33(6):1417–1440, 2004. announced at STOC’97

work page 2004
[5]

Fully dynamic consistent facility location

Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David S aulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. In Conference on Neural Information Processing Systems (NeurIPS), pages 3250–3260, 2019

work page 2019
[6]

Diameter and k-center in sliding windows

Vincent Cohen-Addad, Chris Schwiegelshohn, and Christian S ohler. Diameter and k-center in sliding windows. In International Colloquium on Automata, Languages, and Progr amming (ICALP) , pages 19:1–19:12, 2016

work page 2016
[7]

Tomás Feder and Daniel H. Greene. Optimal algorithms for ap proximate clustering. In Symposium on Theory of Computing (STOC) , pages 434–444, 1988

work page 1988

Show all 28 references

[8]

Dynamic low-stret ch trees via dynamic low-diameter decom- positions

Sebastian Forster and Gramoz Goranci. Dynamic low-stret ch trees via dynamic low-diameter decom- positions. In STOC, pages 377–388, 2019. doi:10.1145/3313276.3316381

2019
[9]

Community detection in graphs

Santo Fortunato. Community detection in graphs. Physics Reports, 486(3):75 – 174, 2010. 11

2010
[10]

Friedler and David M

Sorelle A. Friedler and David M. Mount. Approximation algori thm for the kinetic robust k-center problem. Comput. Geom., 43(6-7):572–586, 2010

2010
[11]

Guibas, and An Thai Nguyen

Jie Gao, Leonidas J. Guibas, and An Thai Nguyen. Deformable spanners and applications. Comput. Geom., 35(1-2):2–19, 2006

2006
[12]

T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci., 38:293– 306, 1985

1985
[13]

A tree structure for dynamic facility location

Gramoz Goranci, Monika Henzinger, and Dariusz Leniowsk i. A tree structure for dynamic facility location. In European Symposium on Algorithms (ESA) , pages 39:1–39:13, 2018

2018
[14]

Cluster analysis and m athematical programming

Pierre Hansen and Brigitte Jaumard. Cluster analysis and m athematical programming. Math. Pro- gram., 79:191–215, 1997

1997
[15]

Clustering motion

Sariel Har-Peled. Clustering motion. Discrete & Computational Geometry , 31(4):545–565, 2004. an- nounced at FOCS’04

2004
[16]

Fast construction of ne ts in low-dimensional metrics and their applications

Sariel Har-Peled and Manor Mendel. Fast construction of ne ts in low-dimensional metrics and their applications. SIAM J. Comput. , 35(5):1148–1184, 2006. announced at SoCG’04

2006
[17]

Dynamic clustering to minimize the sum of radii

Monika Henzinger, Dariusz Leniowski, and Claire Mathieu . Dynamic clustering to minimize the sum of radii. In European Symposium on Algorithms (ESA) , pages 48:1–48:10, 2017

2017
[18]

Small space stream summary for matroid center

Sagar Kale. Small space stream summary for matroid center . In APPROX-RANDOM, pages 20:1–20:22, 2019

2019
[19]

Real-time analysis and visualization of the yfcc100m dataset

Sebastian Kalkowski, Christian Schulze, Andreas Dengel, a nd Damian Borth. Real-time analysis and visualization of the yfcc100m dataset. In Proceedings of the 2015 workshop on community-organized multimodal mining: opportunities for novel solutions , pages 25–30, 2015

2015
[20]

Kariv and S

O. Kariv and S. L. Hakimi. An algorithmic approach to netwo rk location problems. i: The p-centers. SIAM Journal on Applied Mathematics , 37(3):513–538, 1979

1979
[21]

Fast nearest neighbors

Thomas Kollar. Fast nearest neighbors. Technical report , MIT, 2006

2006
[23]

Streaming a lgorithms for k-center clus- tering with outliers and with anonymity

Richard Matthew McCutchen and Samir Khuller. Streaming a lgorithms for k-center clus- tering with outliers and with anonymity. In APPROX-RANDOM, pages 165–178, 2008. doi:10.1007/978-3-540-85363-3\_14

2008 doi
[24]

Expander decompositi on and pruning: Faster, stronger, and simpler

Thatchaphol Saranurak and Di Wang. Expander decompositi on and pruning: Faster, stronger, and simpler. In SODA, pages 2616–2635, 2019. doi:10.1137/1.9781611975482.162

2019 doi
[25]

Graph clustering

Satu Elisa Schaeﬀer. Graph clustering. Computer Science Review, 1(1):27–64, 2007

2007
[26]

Fully dynamic hierarch ical diameter k-clustering and k-center

Melanie Schmidt and Christian Sohler. Fully dynamic hierarch ical diameter k-clustering and k-center. CoRR, abs/1908.02645, 2019. URL: http://arxiv.org/abs/1908.02645

1908 arXiv
[27]

Normalized cuts and image se gmentation

Jianbo Shi and Jitendra Malik. Normalized cuts and image se gmentation. IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888–905, 2000. 12

2000
[28]

Shamma, Gerald Friedland, Benjamin Eli zalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li

Bart Thomee, David A. Shamma, Gerald Friedland, Benjamin Eli zalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li. The new data and new challenges in multi media research. arXiv preprint arXiv:1503.01817, 2015. 13

2015 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [22]

Robert Krauthgamer and James R. Lee. Navigating nets: si mple algorithms for proximity search. In Symposium on Discrete Algorithms (SODA) , pages 798–807, 2004

work page 2004

[2] [1]

Beygelzimer, S

A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for ne arest neighbor. In ICML. ACM, 2006

work page 2006

[3] [2]

Hubert Chan, Arnaud Guerqin, and Mauro Sozio

T.-H. Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dyn amic k-center clustering. In Inter- national World Wide Web Conference (WWW) , pages 579–587, 2018

work page 2018

[4] [3]

Hubert Chan, Arnaud Guerqin, and Mauro Sozio

T.-H. Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dyn amic k-center clustering GitHub Repository. https://github.com/fe6Bc5R4JvLkFkSeExHM/k-center, 2018

work page 2018

[5] [4]

Incremental clustering and dynamic information retrieval

Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev M otwani. Incremental clustering and dynamic information retrieval. SIAM J. Comput. , 33(6):1417–1440, 2004. announced at STOC’97

work page 2004

[6] [5]

Fully dynamic consistent facility location

Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David S aulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. In Conference on Neural Information Processing Systems (NeurIPS), pages 3250–3260, 2019

work page 2019

[7] [6]

Diameter and k-center in sliding windows

Vincent Cohen-Addad, Chris Schwiegelshohn, and Christian S ohler. Diameter and k-center in sliding windows. In International Colloquium on Automata, Languages, and Progr amming (ICALP) , pages 19:1–19:12, 2016

work page 2016

[8] [7]

Tomás Feder and Daniel H. Greene. Optimal algorithms for ap proximate clustering. In Symposium on Theory of Computing (STOC) , pages 434–444, 1988

work page 1988