-
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+1 centers corresponding to points x1,…,xk+1 whose pairwise distances satisfy d(xi,xj)≥2OPT(X) for all i=j. However, this does not necessarily contradict the definition of OPT(X). To obtain a contradiction, one needs to show that d(xi,xj)>2OPT(X) for all i=j. Indeed, since an optimal k-center solution uses only k centers to cover all points with radius OPT(X), the pigeonhole principle implies that at least two of the k+1 points, say xi and xj, must be assigned to the same optimal center c. By the triangle inequality, we then have d(xi,xj)≤d(xi,c)+d(c,xj)≤2OPT(X). This contradicts d(xi,xj)>2OPT(X), but not the non-strict inequality established in the proof. In particular, two points at distance exactly 2OPT(X) may still be covered by a single center with radius OPT(X), provided that the metric space contains a suitable midpoint. Therefore, the proof should be corrected to establish strict pairwise separation.
-
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 k-way MPMD, where elements must be matched into sets of size exactly k [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.
-
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 n and Δ.
-
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”.
-
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.
-
The experiments seem to be restricted to k-median (why?). Also, the baselines used for the experiments are not quite informative about the algorithms’ performance. The authors simply compare the offline k-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 R 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 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), k does not compile as an equation and the citation says “OpenReview.net”. There are other citations where k 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 μ. 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 μ and μ^”.
- Line 207: Thus we → Thus, we
- Section 3’s title: I would write “Online k-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), 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 k-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.
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 1 in the (1+O(ϵ))k center bound under an accurate prediction. One distinction matters in the comparison with Liberty et al. Even if μ^=E[W⋆] exactly, the realized W⋆/μ^ can be arbitrarily large on a rare input. Substituting the prediction for a per-instance cost scale therefore requires an expectation argument.
For k-center, increasing the radius controls the number of centers on inputs whose realized optimum exceeds the predicted scale. For k-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 2k 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.