- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper works on some formulations of proportional clustering and they obtain the following results:
-
They prove that mPJR+ (He 2026, arXiv May 26), a stronger version of the original problem (mPJR), can be verified in polynomial time via flow techniques.
-
The authors proved that mPJR (the original problem) can be optimized in polynomial time, in terms of the k-medians/k-means objective, when the points lie on the real line.
-
The verification of mPJR is coNP-Hard in , improving the coNP-hardness for metric spaces established by (He 2026, Arxiv May 26).
They also present experimental results
Critical strengths
- The optimization of the k-medians and k-means for the line (mPJR) is novel, as far as I can tell, and interesting.
Critical weaknesses
-
The concept of proportional clustering seems reasonable; the idea is trying to ensure that large groups have more (good) representatives than small groups. However, it is unclear why the proportionality conditions mPJR and its variant (mPJR+), addressed in the paper, capture the concept of proportionality well; they are not intuitive to me. In the definition of mPJR, an -cohesive group must have candidates close to every member, but mPJR only guarantees selected centers that are each close to at least one member. The paper does not sufficiently explain why this weaker guarantee is appropriate for capturing clustering proportionality. Maybe this is justified in the existing literature, but from the discussion presented in the body of the paper, I'm not very convinced.
-
Limited novelty and significance relative to previous work.
The novelty and significance of the contributions seem somewhat limited when taking previous results into account. In my assessment, the most novel result is the polynomial-time optimization of the clustering objective subject to mPJR. However, the algorithm only works on the real line, which limits its applicability. The flow-based verification of mPJR+ appears incremental relative to the polynomial-time verification established by He et al. (2026) and the min-cut approach for PJR+ developed by Springham (arXiv, 2026), although the paper includes some extensions such as support for weights and the computation of representation deficits. Finally, the strengthening of the existing coNP-hardness result to is interesting, but I do not find it particularly compelling for the ICLR audience.
Questions for authors
Could you explain in an intuitive way why mPJR and its variants are suitable formulations to capture clustering proportionality?