- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper studies individually-fair MSR k-clustering with at most z outliers. It gives an FPT algorithm in (k + z) that achieves cost (2+ε) times the optimum and a service-fairness factor of 2. It also proves that improving the factor 2 is W[2]-hard.
Critical strengths
The paper studies a problem in clustering, which is a classic task in data analysis and machine learning. The paper provides theoretical guarantees for the performance of the method and lower bound.
Critical weaknesses
The most critical weakness is that it is almost impossible to understand the paper. There is not a proper introduction to introduce the main concepts. Even the abstract is very technical and it assumes that the reader is familiar with the setting and results. There is a lot of terminology that is used without being defined properly, or if it is defined it is not in a linear order and not there is no logical structure. Secondary, there is no literature review, and thus, the authors do not position their paper with the state of the art. In my opinion, in its current form the paper cannot be published, and the required revision go beyond issues that can be fixed during the rebuttal stage. This is a pity, as the theoretical result seems to be potentially interesting.
Questions for authors
I do not have concrete questions, as the convoluted and non-conventional writing does not allow understanding the paper.
Response to Reviewer ertN
Thank you for your time and effort in reviewing our paper. We regret any difficulty our presentation may have caused and would like to clarify several points. We have further revised the paper to improve its clarity and readability.
1. Clarification of the related work and research positioning in response to the comments stating that “there is no literature review” and that the paper is not positioned with respect to the state of the art.
Section 1 of the original submission included a discussion of prior work relevant to our problem, although it may not have been presented clearly enough. In the revised paper, we have further refined and expanded this discussion to clarify the connections to existing research and better position our work within the literature. Specifically, the original submission discussed (i) neighborhood-radius fairness for standard pointwise objectives and assignment-level service, including the work of Liu et al. (2026b) (p. 1, lines 040–050); (ii) fair-MSR work on group-composition constraints and group representation among centers, as well as FPT approximations for mergeable constraints (p. 2, lines 058–069); and (iii) radius/profile guessing and factor-two recentering, which are standard FPT tools for MSR (p. 2, lines 070–082). More importantly, the original submission also explained why these existing approaches do not directly address our problem: neither type of group constraint imposes a point-specific service bound, and radius control alone does not ensure point-specific service. Moreover, the requirement that each retained point be served by its designated center within its personalized bound is non-mergeable (Lemma 5), so generic FPT frameworks for mergeable constraints do not directly apply. Our work addresses this distinct gap by studying service-aware individual fairness for MSR.
2. Clarification of how the main concepts are introduced and defined, and how the paper is structured.
The original paper introduced the main concepts and presented the problem, algorithm, and results in a structured manner. In the revised paper, we have added brief signposting and refined the wording and transitions to make this structure easier to follow. Specifically, Section 1 introduces the motivation and the key distinction between access to a nearby center and the service actually delivered. Section 2, particularly Definition 1, formally defines the main concepts of the problem, including the clustering model, assignments, objective, and fairness conditions. Section 3 introduces nearest-assignment stability (Definition 2), establishes the assignment gap, and proves the non-mergeability of designated service. Section 4 develops and analyzes the algorithm. Section 5 establishes the factor-two service lower bound. Section 6 presents extensions, while Section 7 provides geometric diagnostics and computational verification. This structure is also outlined at the end of the Introduction.
3. Specific revisions to clarify terminology and improve explanations and readability.
We have made several targeted additions and refinements throughout the paper to improve its clarity, organization, and readability. These revisions include providing additional motivation and illustrative examples, clarifying the main concepts and their formal definitions, and adding intuitive explanations of the proposed algorithm and theoretical arguments. We have also improved the presentation of the algorithmic framework, theoretical results, and extensions, as well as refined the transitions and logical connections between sections. Overall, these changes make the paper more coherent and accessible, providing a clearer presentation of the problem formulation, main technical ideas, and contributions while retaining the paper's overall technical framework.
We hope these clarifications and targeted revisions make the paper easier to understand and follow.