{"id":"47999da2-ff37-48d4-8977-57df03bd26bc","arxiv_id":"1908.03948","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A fully dynamic algorithm maintains a (2+ε)-approximate k-center clustering in doubling metrics with polylogarithmic update time independent of k.","lead":"This paper gives a deterministic algorithm that maintains a near-optimal k-center clustering while points are inserted and deleted, with update time that does not depend on the number of centers k in metric spaces of bounded doubling dimension. The result removes a k-dependence present in the previous best dynamic k-center algorithms, making it useful when k is large.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.2 proves only a (2+O(ε))-approximation, not the stated (2+ε); the gap is real but patchable by rescaling ε, so the central algorithm is plausible but Theorem 1.1 as written is unproven.","rationale":"I partially agree with the reader. Their stated weakest assumption is the black-box reliance on [22, Thm 2.5] for deletions in navigating nets; that is genuinely load-bearing because the entire k-independent update time depends on it. However, the more immediate defect is internal: Lemma 3.2's algebra establishes only a 2(1+ε)^2 bound, not 2+ε, and the stated m is slightly too small for the required inequality. This is a concrete gap in the proof of the central theorem. It does not sink the approach, because the standard rescaling of ε repairs the constant while preserving the claimed asymptotic update time, and the KL navigating-net machinery is independent supporting evidence if the cited deletion bound holds. The experimental ACov claims and missing variance information are secondary and do not affect the theoretical core. Since the reader already returned CONDITIONAL and this concern reinforces rather than redirects that verdict, no change to the verdict is needed.","tokens_in":12256,"tokens_out":18296,"duration_ms":196323,"concrete_test":"Re-derive Lemma 3.2 with ε=0.1: set α=20, m=30 or 31, and evaluate 2α/(α−1) · α^{1/m}. If the result exceeds 2.1, the claimed (2+ε) bound is false for that parameter choice. Then repeat the derivation with algorithmic parameter ε''=ε/4, i.e. α=8/ε and m=Cε''^{-1}ln(1/ε''), and verify that the ratio is at most 2+ε. A successful rescaling shows the theorem is salvageable; an unsuccessful one would indicate a deeper issue.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing issue is in the proof of Lemma 3.2. After deriving cost_{p*}/OPT ≤ 2α/(α−1) · α^{1/m}, the paper sets α=2/ε and concludes a bound of 2(1+ε)·(1+ε). That final target is 2+4ε+2ε^2, not 2+ε. Moreover, the stated choice m ≥ ε^{-1}ln2 + ε^{-1}lnε^{-1} is not sufficient to force α^{1/m} ≤ 1+ε, since the required bound is m ≥ ln(2/ε)/ln(1+ε), which is larger. Thus, for the ε used as the algorithm parameter, the theorem's approximation guarantee is not proved. The gap is not structural: running the scheme with a rescaled parameter ε'' ≈ ε/4 (and α=O(1/ε'')) gives (2+ε) with the same asymptotic O(ε^{-1}lnε^{-1}) update time. In addition, the k-independent update time rests entirely on [22, Thm 2.5] for deletions in navigating nets; the present paper does not prove that black box, so if deletion maintenance is more expensive, Theorem 1.1 fails. The Lemma 3.2 algebra error is the more immediate and checkable defect.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12518,"tokens_out":12621,"duration_ms":134591,"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":[{"comment":"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":"Lemma 3.2"},{"comment":"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.","section":"Section 3.2"},{"comment":"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.","section":"Lemma 3.2"}],"minor_comments":[{"comment":"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.","section":"Section 3.1, definition of i*"},{"comment":"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":"Throughout"},{"comment":"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.","section":"Section 4"},{"comment":"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.","section":"References"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nWhere 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.\n\nOverall, 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.","headline":"First k-independent fully-dynamic k-center in doubling metrics, but the (2+ε) guarantee is unproved as written; a rescaling patch fixes it.","tokens_in":13092,"tokens_out":5364,"would_cite":true,"duration_ms":50586,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["k-center clustering","fully dynamic algorithm","doubling dimension","navigating nets","r-nets","aspect ratio","cover trees","clustering queries"],"falsifier":"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.","tokens_in":12045,"feed_emoji":"🎯","tokens_out":6433,"duration_ms":60836,"temperature":0.7,"pith_summary":"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.","feed_headline":"Dynamic k-center clustering runs in polylog update time","feed_subtitle":"A deterministic (2+epsilon)-approximation for doubling-metric data updates in time independent of k.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the dynamic navigating-net data structure used to maintain each hierarchy, with the O(2^{O(kappa)} log Delta log log Delta) per-update bound and the r-net covering and separation invariants.","marker":"[22]"},{"why":"Provides the technique of maintaining several nets with shifted scales that the paper uses to improve the approximation from 8 to 2+epsilon.","marker":"[23]"},{"why":"Defines the fully dynamic k-center model, gives the baseline (2+epsilon)-approximation with O(k^2 eps^{-1} log Delta) update time, and is the practical baseline in the experiments.","marker":"[2]"},{"why":"Supplies cover trees, the implementation substitute for navigating nets used in the experimental variant of the algorithm.","marker":"[1]"}],"fun_headline_variants":["Fully dynamic k-center: polylog updates, (2+ε)-approx","Deterministic (2+ε)-approx k-center with polylog dynamic updates","Dynamic k-center in doubling metrics: polylog time, (2+ε) ratio","Maintain (2+ε)-approx k-center while points change quickly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Fully dynamic k-center: polylog updates, (2+ε)-approx","Deterministic (2+ε)-approx k-center with polylog dynamic updates","Dynamic k-center in doubling metrics: polylog time, (2+ε) ratio","Maintain (2+ε)-approx k-center while points change quickly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00063,"raw_usage":{"total_tokens":2944,"prompt_tokens":1010,"completion_tokens":1934,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":1845}},"tokens_in":626,"tokens_out":1934,"duration_ms":13585,"temperature":1.0,"reasoning_tokens":1845,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:57:37.366579+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the dynamic navigating-net data structure used to maintain each hierarchy, with the O(2^{O(kappa)} log Delta log log Delta) per-update bound and the r-net covering and separation invariants."},{"cited_title":"Hubert Chan, Arnaud Guerqin, and Mauro Sozio","cited_arxiv_id":null,"evidence_quote":"Defines the fully dynamic k-center model, gives the baseline (2+epsilon)-approximation with O(k^2 eps^{-1} log Delta) update time, and is the practical baseline in the experiments."},{"cited_title":"Beygelzimer, S","cited_arxiv_id":null,"evidence_quote":"Supplies cover trees, the implementation substitute for navigating nets used in the experimental variant of the algorithm."}],"review_version":1}