- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper presents an online algorithm for (k,z)-clustering, where z=1 indicates k-median and z=2 indicates k-means. Assuming an alpha-approximation algorithm for offline (k,z)-clustering, the proposed online algorithm claims a (1+epsilon)alpha approximation algorithm for the online (k,z)-clustering problem.
Critical strengths
(Online) clustering is a fundamental ML primitive, and the claimed result is a good improvement over the state-of-the-art.
Critical weaknesses
Unfortunately, the paper is not comprehensible. There is too much unconventional notation (for example, what does "positive records" stand for?). The development follows a non-logical sequence of steps, where claims are made and concepts are discussed without having been defined earlier. The precise streaming setting is not defined. The optimization objective for the online problem is not precisely defined. A lot of notation that is used is not defined. Math concepts are defined without proper discussion of what they mean. The claimed result sounds interesting, but unfortunately it is not possible to follow the logical flow.
Questions for authors
I do not have concrete questions, since the convoluted and non-conventional writtng does not allow understanding the paper.
2 comments
Dear Reviewer 3oeg,
Thank you for your review.
The authors have responded to your concerns and revised the manuscript. Could you please check whether these revisions address your main concerns?
Your feedback would be appreciated.
Regards, AC
The review states that the streaming setting and optimization objective are not defined. These statements are contradicted by Section 3 of the original submission. All line references below refer to that version.
Specifically, lines 134–135 define the metric space and fixed feasible-center set. Lines 139–143 introduce the weighted input and explicitly display the clustering objective and optimum. Lines 145–150 specify the output cardinality constraint and define cumulative center-addition recourse. Theorem 3.1 then states the approximation guarantee at every prefix and the recourse bound. These definitions are in the main paper, before the algorithm and its analysis.
“Positive records” means points with positive weights, represented as pairs (p,w) in line 139. We can make this wording more explicit, but a terminology clarification does not justify the assertion that the model and objective are undefined.
The review also assigns the lowest soundness score without identifying a specific incorrect claim, invalid proof step, or missing assumption. We ask the reviewer to correct the statements above and reassess the evaluation accordingly. Any remaining soundness concern should identify the mathematical claim or argument in question so that we can respond substantively.