acceptodds
Under review as a conference paper at ICLR 2027

Online Clustering with Stochastic Arrivals

Abstract

We study online -clustering under strict consistency constraints: points are irrevocably assigned to a cluster and there is zero recourse (centers cannot be moved or closed). While achieving bounded costs under these constraints is impossible in the worst case without significantly relaxing the problem, we introduce the first framework for *online clustering with stochastic arrivals* to circumvent these adversarial lower bounds. By making mild stochastic modeling assumptions, we provide novel algorithms for the -center and -median objectives that achieve -approximations. Our algorithms strictly adhere to zero recourse and irrevocable assignments by utilizing a parsimonious amount of resource augmentation, opening at most centers in expectation for any constant . Moreover, our algorithms have two additional properties that are extremely important in practice. First, they need only minimal information about the distribution: the expected cost of the optimal solution. Second, our algorithms are robust to model mis-specification — the performance of our algorithms smoothly degrades as our estimate of this expectation differs from the true expectation. Put together, these two properties mean that we need only to assume a weak estimate of one particular statistic about the distribution, rather than assuming full knowledge. We validate our theoretical results with experiments demonstrating the superior performance of our algorithms when distributional information is available.

Primary area:
optimization
Keywords:
Algorithms with Predictions, Online Clustering, k-center, k-median

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_CMosOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies online metric kk-center and kk-median clustering under strict consistency constraints: zero recourse on centers selection and irrevocable point-to-center assignments upon arrival. Achieving a bounded competitive ratio while opening at most kk centers is impossible in the adversarial model. The authors show in Proposition 12 that it remains impossible even under i.i.d. arrivals. The proof relies on the standard hard case for online clustering (and online learning as a whole). That is, a very rare event with a very high cost/loss. They conclude that, if the total cost is (somehow) a priory known or estimates, online clustering is approximable.

Critical strengths

Clean Theoretical Framing of Consistent Online Clustering with Minimal Distributional Advice and Resource Augmentation: The paper identifies a clean and practical middle ground between worst-case adversarial impossibilities and full distributional knowledge in consistent online clustering. It explains why (1+ϵ)k(1+\epsilon)k resource augmentation is information-theoretically indispensable even under i.i.d. arrivals when the distribution is fully known in advance. It shows that a single scalar statistic is sufficient to reduce the number of opened centers from Ω(klog⁡n)\Omega(k \log n) in worst-case consistent clustering down to (1+O(ϵ))k(1+O(\epsilon))k in expectation while maintaining an O(1/ϵ2)O(1/\epsilon^2)-competitive expected cost. The resulting algorithms are simple, run in O(nk)O(nk) time, and require no spatial predictions of cluster centers.

Critical weaknesses

Limited Algorithmic and Analytical Novelty Relative to Liberty et al. (2016) and Meyerson (2001), and Suboptimal Underestimation Robustness from Dropping Phase Doubling.

The paper positions its k-median algorithm (Algorithm 2) as a novel alternative to prior consistent clustering methods that require Ω(klog⁡n)\Omega(k \log n) centers, notably Liberty, Sriharsha, and Sviridenko (ALENEX 2016). However, a direct comparison reveals that Algorithm 2 is simply a single static-cost phase of the algorithm of Liberty et al. (2016) (which itself adapts Meyerson, FOCS 2001), and that the elimination of the two logarithmic factors in Liberty et al.'s O(klog⁡nlog⁡W∗w∗)O\left(k \log n \log \frac{W^*}{w^*}\right) center bound is an immediate consequence of the two modeling assumptions rather than a new algorithmic mechanism:

In Liberty et al. (2016), the log(W⋆/w⋆)log(W^{\star}/w^{\star}) factor arises solely because the algorithm is only given a crude lower bound w⋆≤W⋆w^\star \le W^\star and must double the facility cost frf_r across phases. Supplying an estimate μ^\widehat{\mu} within a constant factor of μ=E[W⋆]\mu = \mathbb{E}[W^\star] immediately sets log⁡(W⋆/μ^)=O(1)\log(W^\star/\widehat{\mu}) = O(1).

In Liberty et al. (2016), the log⁡n\log n factor arises solely from adversarial arrival order, where an adversary can present 1+log⁡n1 + \log n concentric rings Si,τ⋆={v∈Si⋆:∥v−ci⋆∥2∈(2τ−1Ai⋆,2τAi⋆]}S_{i,\tau}^\star = \{v \in S_i^\star : \|v - c_i^\star\|^2 \in (2^{\tau-1}A_i^\star, 2^\tau A_i^\star]\} from the outside in, forcing 11 center per ring and requiring f≍W⋆klog⁡nf \asymp \frac{W^\star}{k \log n}. Under random arrival order (exchangeable distributions), Meyerson (2001) already showed that the log⁡n\log n rings collapse into a two-part split (a "close" core Si,c⋆S_{i,c}^\star of radius ≤Ai∗/ϵ\le A_i^*/\epsilon and a "far" set Si,f⋆S_{i,f}^\star of size ≤ϵ∣Si⋆∣\le \epsilon |S_i^\star|), removing the log⁡n\log n factor completely.

This is further supported by the fact that the key inductive step in Lemma 10 (E[∑i∈Sc(c⋆)pi1{i≤j∗}]≤1\mathbb{E}[\sum_{i \in S_c(c^\star)} p_i \mathbf{1}\{i \le j^*\}] \le 1) is identical to Lemma 1 of Liberty et al. (2016).

Consequently, if Liberty et al. (2016) is run under the exact same exchangeable arrival model with facility cost f=μ^ϵ2kf = \frac{\widehat{\mu}}{\epsilon^2 k}, it yields the exact same (1+O(ϵ)+O(ϵ)μμ^)k\left(1 + O(\epsilon) + O(\epsilon)\frac{\mu}{\widehat{\mu}}\right)k expected center bound and 1ϵ2((1+O(ϵ))μ^μ+O(ϵ))μ\frac{1}{\epsilon^2}\left((1+O(\epsilon))\frac{\widehat{\mu}}{\mu} + O(\epsilon)\right)\mu expected cost bound (for both kk-median and kk-means).

Furthermore, because Algorithm 2 in this submission drops Liberty et al.'s phase-doubling mechanism and keeps f=μ^ϵ2kf = \frac{\widehat{\mu}}{\epsilon^2 k} fixed, its expected center count blows up linearly as Θ(ϵμμ^k)\Theta\left(\epsilon \frac{\mu}{\widehat{\mu}} k\right) whenever μ^\widehat{\mu} underestimates μ\mu (e.g., under distribution shift or when a 5% sample misses a heavy-tailed cluster). By contrast, retaining Liberty et al.'s phase-doubling rule (doubling frf_r whenever 2k2k centers are opened in a phase, analogous to what the authors do for kk-center in Algorithm 1) bounds the deterministic first-close-center count by kk and applies Markov's inequality to the excess centers qr′q'_r, reducing the center blowup under underestimation from linear Θ(μμ^k)\Theta\left(\frac{\mu}{\widehat{\mu}} k\right) to logarithmic O(klog⁡μμ^)O\left(k \log \frac{\mu}{\widehat{\mu}}\right) while preserving O(μ/ϵ2)O(\mu/\epsilon^2) cost.

Questions for authors

If one runs Algorithm 1 of Liberty et al. (2016) in the exchangeable arrival model initialized at f1=μ^ϵ2kf_1 = \frac{\widehat{\mu}}{\epsilon^2 k} and doubles frf_r only when 2k2k centers are opened in phase rr (removing the log⁡n\log n factor that was only needed for adversarial arrival order), doesn't this achieve the exact same (1+O(ϵ))k(1+O(\epsilon))k center bound and O(μ/ϵ2)O(\mu/\epsilon^2) cost bound when μ^≈μ\widehat{\mu} \approx \mu, while strictly improving the number of opened centers under underestimation (μ^≪μ\widehat{\mu} \ll \mu) from linear O(μμ^k)O\left(\frac{\mu}{\widehat{\mu}} k\right) to logarithmic O(klog⁡μμ^)O\left(k \log \frac{\mu}{\widehat{\mu}}\right)? Why did the authors include phase scaling for kk-center (Algorithm 1) but omit it for kk-median (Algorithm 2)?

1 comment

Thank you for your detailed review. We agree that Algorithm 2 uses Meyerson’s opening rule at a fixed facility cost and is closely related to a single phase of Liberty et al. The contribution we claim is the simultaneous expected cost and center guarantee, particularly the leading 11 in the (1+O(ϵ))k(1+O(\epsilon))k center bound under an accurate prediction. One distinction matters in the comparison with Liberty et al. Even if μ^=E[W⋆]\hat\mu=\mathbb E[W^\star] exactly, the realized W⋆/μ^W^\star/\hat\mu can be arbitrarily large on a rare input. Substituting the prediction for a per-instance cost scale therefore requires an expectation argument.

For kk-center, increasing the radius controls the number of centers on inputs whose realized optimum exceeds the predicted scale. For kk-median, a fixed facility cost already suffices for the stated tradeoff and gives explicit bounds in terms of prediction error. We agree that doubling the facility cost after 2k2k openings is a natural extension. To establish the proposed improvement, one would need to control the assignment cost at the adaptively increased facility costs as well as the expected number of phases. Our analysis leaves that question open, and we do not claim that the linear dependence on underestimation in our center-count upper bound is tight.

Reviewer_MqNqOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies online kk-center and kk-median clustering, where the sequence of points is drawn from some distributions. Specifically, the authors consider a learning-augmented setting, where algorithm are given access to a prediction of the expected optimal cost. For both online kk-center clustering and online kk-median clustering, the authors devise algorithms with certain guarantees on their competitive ratios and the number of opened centers.

Critical strengths
  1. The paper solves a crucial setting that has been overlooked in the literature (specifically, learning-augmented algorithms for online clustering with stochastic arrivals).

  2. Even though the paper uses well-known techniques, its guarantees are non-trivial and interesting enough.

Critical weaknesses
  1. Some proofs are incomplete and the arguments provided for them do not fully establish the result they claim to establish. Though those are fixable, this adds to my overall impression of informalities and inaccuracies throughout the paper (see the other weaknesses that I list below). For example, the proof of Lemma 4 is quite incomplete. The claimed contradiction in the two paragraphs of the proof does not seem to follow from the inequalities as stated. The argument establishes that the algorithm has opened k+1k+1 centers corresponding to points x1,…,xk+1x_1,\ldots,x_{k+1} whose pairwise distances satisfy d(xi,xj)≥2OPT(X)d(x_i,x_j)\geq 2\mathrm{OPT}(X) for all i≠ji\neq j. However, this does not necessarily contradict the definition of OPT(X)\mathrm{OPT}(X). To obtain a contradiction, one needs to show that d(xi,xj)>2OPT(X)d(x_i,x_j)>2\mathrm{OPT}(X) for all i≠ji\neq j. Indeed, since an optimal kk-center solution uses only kk centers to cover all points with radius OPT(X)\mathrm{OPT}(X), the pigeonhole principle implies that at least two of the k+1k+1 points, say xix_i and xjx_j, must be assigned to the same optimal center cc. By the triangle inequality, we then have d(xi,xj)≤d(xi,c)+d(c,xj)≤2OPT(X)d(x_i,x_j)\leq d(x_i,c)+d(c,x_j)\leq 2\mathrm{OPT}(X). This contradicts d(xi,xj)>2OPT(X)d(x_i,x_j)>2\mathrm{OPT}(X), but not the non-strict inequality established in the proof. In particular, two points at distance exactly 2OPT(X)2\mathrm{OPT}(X) may still be covered by a single center with radius OPT(X)\mathrm{OPT}(X), provided that the metric space contains a suitable midpoint. Therefore, the proof should be corrected to establish strict pairwise separation.

  2. There are several missing related works and the existing discussion is incorrect, which makes the positioning in the literature incomplete and misleading. Adding the missing prior works and fixing the discussion also changes several novelty claims. For instance, in the abstract, the authors claim “we introduce the first framework for online clustering with stochastic arrivals”, which is incorrect.

    • In section 2.1, the authors discuss the works by Bhattacharjee & Moshkovitz (2021), Moshkovitz (2021) and Hess et al. (2021), where each one of them considers a certain form of stochastic arrivals. Similarly to the current paper, Bhattacharjee & Moshkovitz (2021) consider settings where the data is sampled from a “natural” distribution like a mixture of Gaussians, while Hess et al. (2021) and Moshkovitz (2021) study random arrival orders. This makes statements like “Distributional inputs have been considered in the offline setting for k-clustering (Cormode & McGregor, 2008; Guha & Munagala, 2009), but little is known when we move to the online setting” in lines 62-63 incorrect.

    • Stochastic arrivals have also been studied in online non-centroid clustering. In particular, a special case is the Min-cost Perfect Matching with Delays (MPMD) [1,2,3] where clusters are of size exactly two. MPMD was studied under stochastic arrivals [7]. It has also been generalized to kk-way MPMD, where elements must be matched into sets of size exactly kk [4,5]. The most relevant paper is [6], where assignments need not be immediate and the objective is non-centroid clustering with delay costs. In fact, [6,7] obtain a constant approximation without giving algorithms access to the expected cost of the optimal solution. So the authors should make a better distinction here when they say “we introduce the first framework for online clustering with stochastic arrivals”.

    • On that note, the paper should be more clear about the meaning of “stochastic arrivals” (e.g., in the abstract and introduction). Existing works consider various probabilistic input models, including random-order arrivals, independently sampled points and more general stochastic processes. These models differ in their assumptions about the randomness, independence and distributional information available to the algorithm. The authors must thus distinguish when comparing existing results and also make the distributional assumptions assumed in this work clear from the start instead of using generic statements like “stochastic arrivals” and “by making mild stochastic modeling assumptions”.

    • There are many other works that are left uncited such as [8,9,10].

    • The related work in section 1.2 is also just a list of results without any comparisons between the current paper and prior work. The related work should also discuss what is missing and how the current paper treats those missing parts.

  3. Several other statements are also imprecise and should be revised. For example, the authors actually consider learning-augmented online algorithms (or algorithms with predictions) without explicitly saying so from the beginning and they also don’t use the correct terminology for that topic. Together with the previous issues, this oversells the results.

    • In the abstract, after saying that the expected cost of the optimal solution is given to the algorithm, the next statement says “the performance of our algorithms smoothly degrades as our estimate of this expectation differs from the true expectation”. So the algorithm is actually given access to a prediction of the expected cost of the optimal solution. The authors should therefore revise the entire paper to make the setting explicit and frame the paper around algorithms with predictions. Specifically, they should explicitly state that they consider learning-augmented algorithms right from the start, so the assumption about having access to the expected cost of the optimal solution should appear before the approximation and resource augmentation results are stated in the abstract and introduction. Then, as customary in the literature on algorithms with predictions, the authors should more accurately discuss their guarantees using the common terminology of consistency and robustness.

    • Due to this inaccurate discussion and since the paper also considers resource augmentation, I believe the title “Online Clustering with Stochastic Arrivals” is a bit too misleading and vague to actually describe the paper’s true setting. The title should be modified to something like “Learning-Augmented Online Clustering with Stochastic Arrivals and Resource Augmentation”. This accurately reflects the paper’s content.

    • The abstract and the introduction classify the expected cost of the optimal solution as “only minimal information about the distribution”. I would consider the expected cost of the optimal solution to be a very limited form of distributional information since it provides only a single statistic rather than any detailed knowledge of the underlying distribution. However, I would be cautious about calling it minimal information, as even this single value can be quite informative for an algorithm, for example when setting thresholds or guiding decisions.

    • The discussion in lines 48-56 uses many undefined notations, like nn and Δ\Delta.

    • Lines 60-61 contains a rather generic motivation for considering distributional assumptions, as statistical regularities arise in many real-world data-generating processes. It would be helpful to explain why such regularities justify the specific stochastic arrival model considered here rather than stochastic models more generally. The notion of “statistical regularity” used throughout the paper is also broad and somewhat vague. It would be more appropriate to clarify what specific regularities are meant here and how they motivate the particular distributional assumptions adopted in this work.

    • Actually, the proposed research questions in lines 65-72 are formulated at a very high level and are too vague to identify concrete mathematical problems. Several central notions, such as “statistical regularity”, “level of information”, “operate effectively” and “degrades slowly and smoothly” are either undefined or ambiguous. Also, the questions do not specify the performance measures, distributional assumptions or lower bounds under consideration. As currently stated, they read more like broad research directions than well-defined research questions. A more precise formulation would help clarify the intended contributions and the specific algorithmic challenges being addressed.

    • The authors repeatedly use the term “a parsimonious amount of resource augmentation”, which is rather unconventional and imprecise. It would be clearer to use standard terminology, such as “limited resource augmentation”.

  4. In terms of techniques, the paper lacks technical depth. All techniques are well-established approaches that have already been used elsewhere. For example, Algorithm 1 is explicitly claimed to use standard techniques and Algorithm 2 adapts Meyerson’s algorithm and its analysis (see lines 315-317). For Algorithm 1, a similar radius-based approach has also been used by, e.g., Mari et al. [7] (though they don’t rely on predictions), which is cited below. As said earlier, this paper (among others) is not cited.

  5. The experiments seem to be restricted to kk-median (why?). Also, the baselines used for the experiments are not quite informative about the algorithms’ performance. The authors simply compare the offline kk-median solution and an oracle-assisted baseline. That comparison is not quite complete. I would have expected more natural online baselines. Here are a few examples:

    • In lines 262-263, the authors say that simply doubling RR in each round is too naïve, so I would have expected them to test this empirically and to see whether their currently unsubstantiated claim that “we could open much more than (1+ϵ)k(1 + \epsilon)k centers” actually holds.

    • Bhattacharjee & Moshkovitz (2021) consider settings where the data is sampled from a natural distribution like a mixture of Gaussians, so why not compare against them?

    • Random assignment is also a natural baseline.

Other comments

  • Even though zero recourse has already been explicitly defined as prohibiting changes to cluster centers (e.g., in the abstract), “zero recourse and irrevocable assignments” is still a bit ambiguous because recourse is often used more broadly to describe changes to previous decisions, including assignments. To make the distinction immediately clear, I would recommend writing something like “zero recourse for cluster centers and irrevocable point assignments”.
  • There are many weird issues with citations’ formatting. For example, in the paper by Ergun et al. (2022), kk does not compile as an equation and the citation says “OpenReview.net”. There are other citations where kk is not compiled as an equation. The paper by Fotakis et al. (2025) includes “Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 - March 4, 2025, Philadelphia, PA, USA”. Some citations include DOIs, URLs and so on while some do not include them. The authors should go over all citations and make them consistent.
  • Though the paper contains only 5 long hyphens, I suggest removing them entirely because they don’t look visually good.
  • The first three paragraphs of section 1 should use \citep instead of \citet.
  • Throughout the paper: iid → i.i.d.
  • Line 104: We again can → We can again
  • Minor comment: I must say that the writing “tone” is somewhat inconsistent. Up to line 104, the tone was mostly academic, but then the text shifted to a more spoken tone as if this part was written by a completely different person (“This is a particularly nice class for us”, “This isn’t quite true, though, and moreover we do not actually know μ\mu. So our actual algorithm…” seem more like spoken language). I suggest making the writing consistent throughout the paper.
  • Line 117: there is significant distribution shift → there is a significant distribution shift
  • Line116 says that the subsequent discussion is the intuition for the bounds in Theorems 1 and 2, but it’s more of an interpretation together with a discussion about a special case.
  • Line 126: “pays based on” is somewhat awkward in mathematical writing. A more natural formulation would be “Our algorithm incurs a cost that depends only on the multiplicative gap between μ\mu and μ^\hat \mu”.
  • Line 207: Thus we → Thus, we
  • Section 3’s title: I would write “Online kk-Center Clustering under Stochastic Arrivals”.
  • Lines 262-267: this paragraph is not properly punctuated since it is missing commas in the right places (e.g., after OPT(X)OPT(X), after “Here” and so on).
  • Line 265: Maybe say what is the “better starting point” also in the text.

[1] Emek, Yuval, Shay Kutten, and Roger Wattenhofer. "Online matching: haste makes waste!." STOC 2016.

[2] Azar, Yossi, Ashish Chiplunkar, and Haim Kaplan. "Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays." SODA 2017.

[3] Ashlagi, Itai, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer. "Min-cost bipartite perfect matching with delays." APPROX/RANDOM 2017.

[4] Naonori Kakimura and Tomohiro Nakayoshi. “Deterministic primal-dual algorithms for online kk-way matching with delays”. Theoretical Computer Science, 2025.

[5] Yasushi Kawase and Tomohiro Nakayoshi. “Online Matching with Delays and Size-Based Costs”. STACS 2025.

[6] Cohen, Saar. (2026). Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals. AAMAS 2026.

[7] Mathieu Mari, Michał Pawłowski, Runtian Ren, and Piotr Sankowski. “Online matching with delays and stochastic arrival times”. Theory of Computing Systems, 69(1):1-46, 2025.

[8] Cohen-Addad, Vincent, Silvio Lattanzi, Andreas Maggiori, and Nikos Parotsidis. "Online and consistent correlation clustering." ICML 2022.

[9] Christou, Dimitrios, Stratis Skoulakis, and Volkan Cevher. "Efficient online clustering with moving costs." NeurIPS 2023.

[10] Fotakis, Dimitris, Georgios Piliouras, and Stratis Skoulakis. "Efficient online learning for dynamic k-clustering." ICML 2021.

Questions for authors

To fully validate the empirical results, the authors should have also done experiments that include:

  1. online kk-center clustering.
  2. comparison to more relevant baselines (as mentioned above). This would show whether the methods are practically relevant as the authors claim and also verify whether unsubstantiated claims like “we could open much more than (1+ϵ)k(1 + \epsilon)k centers” in lines 262-264 actually holds. I would very much appreciate any response on this matter.
1 comment

Thank you for your detailed review and for pointing out the strict inequality needed in Lemma 4. Algorithm 1 assigns to an existing center whenever the distance is at most RR. A new center is therefore strictly farther than RR from every existing center. In the packing argument, the k+1k+1 selected points are thus pairwise at distance strictly greater than 2OPT(X)2\mathrm{OPT}(X), which gives the required contradiction.

We agree that “first framework for online clustering with stochastic arrivals” is too broad. Our question is how close the expected center count can be to kk when centers are permanent, assignments are immediate and irrevocable, and the algorithm receives a prediction of the expected optimal cost. The kk-center result allows arbitrary distributions over sequences, while the kk-median result assumes exchangeability. Earlier random-order no-substitution results permit assignments in hindsight. We should make these distinctions explicit in the abstract and introduction.

The experiments illustrate the cost–center tradeoff for kk-median at k=10k=10. They leave open the empirical comparison with implementable online baselines and the behavior of the kk-center algorithm. We agree that the empirical claim in the abstract should reflect that scope.

Reviewer_Z6npOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies stochastic online kk-center and kk-median clustering under strict consistency constraints, requiring irrevocable assignments and zero recourse. The authors propose two algorithms using only an estimate μ^\widehat{\mu} of the expected optimal cost μ\mu.

For kk-center, the paper achieves an expected approximation ratio of 1ε2(1+μ^μ)\frac{1}{\varepsilon^2}(1+\frac{\widehat{\mu}}{\mu}), while opening at most (1+ε1−εμμ^)k(1+\frac{\varepsilon}{1-\varepsilon}\frac{\mu}{\widehat{\mu}})k centers in expectation.

For kk-median, a randomized center-opening algorithm achieves an expected approximation ratio of 1ε2((1+O(ε))μ^μ+O(ε))\frac{1}{\varepsilon^2}((1+O(\varepsilon))\frac{\widehat{\mu}}{\mu}+O(\varepsilon)), using at most (1+O(ε)+O(ε)μμ^)k(1+O(\varepsilon)+O(\varepsilon)\frac{\mu}{\widehat{\mu}})k centers in expectation.

Critical strengths

The consistency-constrained model is meaningful, the prediction requirements are limited, and the budget lower bound helps motivate resource augmentation.

Critical weaknesses
  • When k=1k=1, Algorithm 1 initializes s=1s=1 but does not immediately check the phase-ending condition. If the second arrival opens a center, ss becomes 22, and the condition s=ks=k is never satisfied again.

  • Lines 790–793 replace E[pj∣Ej]E[p_j\mid E_j] with E[pj]E[p_j]. Random arrival order does not establish independence, since pjp_j depends on the preceding history. Please justify this transition rigorously.

  • The kk-center algorithm shares the threshold-and-doubling structure of Charikar et al. (1997), while Algorithm 2 follows Meyerson’s (2001) online facility-location approach. Although classical incremental clustering permits cluster merging and therefore does not directly satisfy the present consistency constraints, the paper should clarify which new algorithmic ideas and proof techniques are required beyond adapting these established frameworks. The experiments should also include a natural greedy extension of these classical algorithms.

  • Please include implementable online baselines, controlled prediction errors, and varying kk. Some reported results are outside the proven range ε≤1/2\varepsilon\le1/2.

Questions for authors

See weaknesses.

1 comment

Thank you for your careful review. We agree that pjp_j depends on the arrival history. The following swap argument replaces lines 790–793.

Fix the multiset, a far point ii, and a close point jj in the same optimal cluster. Let f=μ^/(ϵ2k)f=\hat{\mu}/(\epsilon^2 k). If jj arrives first, permanence of centers and the triangle inequality give pi≤pj+d(i,j)/fp_i\le p_j+d(i,j)/f. If ii arrives first, swap ii and jj, keeping the random coins fixed by position. The prefix before the earlier position is identical in both runs, so pip_i in the original run is at most pjp_j in the swapped run plus d(i,j)/fd(i,j)/f. The swap maps orders in which ii arrives first bijectively to equally likely orders in which jj arrives first. Combining the two cases gives E[pi]≤2E[pj]+d(i,j)/f\mathbb{E}[p_i]\le 2\mathbb{E}[p_j]+d(i,j)/f. Averaging over close points jj and summing over far points ii, the first term is bounded by 2(∣Sf∣/∣Sc∣)∑j∈ScE[pj]2(|S_f|/|S_c|)\sum_{j\in S_c}\mathbb{E}[p_j]. Applying Lemma 10, ∣Sf∣/∣Sc∣≤ϵ/(1−ϵ)|S_f|/|S_c|\le\epsilon/(1-\epsilon), and d(i,j)≤d(i,c⋆)+d(j,c⋆)d(i,j)\le d(i,c^\star)+d(j,c^\star) gives the stated asymptotic bound.

We also agree about the initialization when k=1k=1. In this case, Algorithm 1 can retain the first point as its sole center. By the triangle inequality, every assignment distance is at most 2OPT(X)2\mathrm{OPT}(X). We agree that the classical opening rules deserve clearer attribution and that implementable online baselines, a wider range of kk values, and controlled prediction errors would strengthen the experiments. The results for ϵ>1/2\epsilon>1/2 are empirical observations outside the theorem’s range.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.