acceptodds
Under review as a conference paper at ICLR 2027

When a Nearby Center Is Not Enough: Service-Aware Individual Fairness for Min-Sum-Radii Clustering

Abstract

Neighborhood-radius individual fairness typically bounds each point's distance to the selected center set, not to the center that actually serves it. For standard pointwise objectives, nearest-center reassignment enforces fair service without increasing cost. We formalize nearest-assignment stability—coordinatewise no-farther reassignment cannot increase cost—as a sufficient transfer condition. In contrast, minimum sum of radii (MSR) depends on the realized partition and admits a linear gap: on a tree with points and standard -neighbor radii, the exact selected-set-fair and service-aware optima are and , respectively. To our knowledge, we give the first study of service-aware individually fair MSR, requiring every retained point's assigned center to meet its personalized service bound. To handle this non-mergeable constraint, we introduce minimum-priority capture, which constructs centers and assignments jointly. For arbitrary priorities, the algorithm is deterministic and fixed-parameter tractable (FPT) in for fixed . Whenever exact -service is feasible, it returns at most centers and at most outliers, with cost at most times the exact-service optimum and service-fairness factor . We establish a matching service lower bound: for every fixed , a budget-preserving deterministic FPT algorithm guaranteeing factor on exact-service-feasible inputs would imply , even with standard neighborhood radii, no outliers, and unrestricted cost. The framework extends to fixed polynomial-time computable monotone symmetric norms of cluster radii and to min-sum-diameters.

Primary area:
learning theory
Keywords:
fair clustering, individual fairness, service-aware individual fairness, min-sum-radii clustering, approximation algorithms, fixed-parameter tractability

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_ertNOpenReview ↗
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.

1 comment
AuthorsOpenReview ↗

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.

Reviewer_hucGOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies individually fair minimum sum of radii clustering, distinguishing fairness of proximity to selected centers from fairness of actual assignments. It formalizes a sufficient condition for transferring between these notions without increasing cost and constructs tree instances exhibiting a Θ(k)\Theta(k) gap between their optimal costs. The proposed minimum priority capture algorithm is deterministic and FPT in the center and outlier budgets for fixed ε\varepsilon. Whenever exact service fairness is feasible, it achieves cost at most 2+ε2+\varepsilon times the exact service optimum and service stretch 2, while preserving both budgets. A matching hardness result rules out any fixed service factor below 2 for deterministic FPT algorithms unless FPT=W[2]\mathrm{FPT}=\mathrm{W[2]}, even with standard neighborhood radii and no outliers. Extensions cover monotone symmetric norms of cluster radii and minimum sum of diameters. Validation includes exact comparisons on small Euclidean data subsamples and exhaustive or randomized checks on tiny metric instances.

Critical strengths
  1. A natural problem formulation with solid theoretical guarantees. Building on established research on individual fairness, the paper naturally extends fairness of access to selected centers to fairness of actual assignments. This distinction raises a meaningful optimization problem for objectives that depend on the realized partition. The theoretical treatment is solid, providing a deterministic FPT algorithm with a 2+ε2+\varepsilon cost approximation and service stretch 2 while preserving the center and outlier budgets. Experiments on small instances provide complementary validation. The combination of a natural formulation and substantive theoretical guarantees is the main reason for my positive assessment.

  2. Clear presentation and organization. The paper is well structured, with a logical progression from the problem formulation to the algorithm and its analysis. The pseudocode makes the search procedure easier to understand and connects it effectively to the subsequent proofs. This clarity helps readers follow the technical arguments and assess the contributions.

Critical weaknesses

None. There is still some room for improvement, but they cannot be seen as critical weaknesses. See Questions For Authors below.

Questions for authors
  1. Potential improvement of the cost factor. Is it possible to obtain a smaller cost approximation factor while retaining service stretch 2 and preserving both budgets? In particular, do the authors expect a cost factor below 2 to be achievable? I view this as a future research direction and would welcome any partial results or insights into the prospects and main obstacles.

  2. Experiments on larger instances. For a theoretical paper, the current experiments provide appropriate supporting evidence for the theoretical results. Additional experiments on larger instances, if feasible, would further strengthen this evidence. Could the authors provide runtime results for larger values of nn than 20, initially keeping the other parameters fixed? If such tests are computationally impractical, explaining the main bottlenecks would also help readers understand the computational scope of the method.

  3. Potential applications. Could the authors describe a concrete application in which minimizing the sum of cluster radii and imposing individualized bounds on actual assignment distances are jointly meaningful? Although an immediate application is not necessary for the theoretical contribution, a plausible scenario would strengthen the practical motivation and help readers understand where the distinction between nearby centers and designated service matters.

3 comments
AuthorsOpenReview ↗

Response to Reviewer hucG

We sincerely thank the reviewer for these thoughtful questions and constructive suggestions. We particularly appreciate the reviewer’s recognition of the theoretical contribution and the clear presentation of our work. We address the three questions in turn.

Question 1: Potential improvement of the cost factor. Is it possible to obtain a smaller cost approximation factor while retaining service stretch 2 and preserving both budgets? In particular, do the authors expect a cost factor below 2 to be achievable? I view this as a future research direction and would welcome any partial results or insights into the prospects and main obstacles.

Response: Thank you for this thoughtful and insightful question. We are particularly interested in this problem and believe that obtaining a smaller cost approximation factor while retaining service stretch 2 and preserving both the center and outlier budgets is a valuable and promising direction for further research. We would like to share three observations and potential directions.

1. A partial improvement in general metric spaces.

We observe that a simple modification of our algorithm yields a cost approximation factor of 2−12k2-\frac{1}{2k}, while maintaining service stretch 2, i.e., d(x,σ(x))≤2λρ(x)d(x,\sigma(x))\leq 2\lambda\rho(x), and preserving both budgets. The key idea is to enumerate one center for the cluster corresponding to the largest guessed radius before applying our minimum-priority capture procedure. Along the appropriate branch, this cluster can be captured at its original guessed radius rather than twice that radius, while the remaining clusters are handled by our existing analysis. Since the largest radius accounts for at least a 1/k1/k fraction of the total guessed cost, this yields a strict improvement below 2 while retaining FPT running time. We acknowledge that the improvement depends on kk and becomes smaller as kk increases.

2. The challenge of a kk-independent improvement.

We believe that achieving a cost factor of 2−δ2-\delta, for some fixed constant δ>0\delta>0 independent of kk, is an even more interesting open question, which we have not yet resolved. A key obstacle in our current framework is the factor-two loss from recentering: the minimum-priority pivot may be at distance nearly twice the optimal radius from other points in its cluster. Such losses may occur across many clusters, making it difficult to obtain a constant improvement in the total cost through a small number of center guesses. Moreover, existing techniques for unconstrained MSR do not directly extend to our setting, since their merging or replacement arguments may violate the point-specific service constraints. We think that overcoming these obstacles requires new techniques for jointly selecting centers and constructing service-aware assignments. In future work, we will try to develop some new techniques to make progress on this problem.

3. A promising direction in doubling metrics.

We also see potential for stronger results in metric spaces of bounded doubling dimension. Their geometric structure may allow us to construct small local nets of candidate centers around each pivot. By enumerating these candidates, rather than using the pivot itself as the center, one may be able to reduce the recentering loss substantially while preserving the service constraints and both budgets. This suggests a possible route toward a (1+ε)(1+\varepsilon) cost approximation in such structured metric spaces. We view this as a promising direction that deserves further investigation rather than a fully established result.

We are grateful to the reviewer for highlighting this important question. We believe it opens up several interesting directions beyond the present work, and we would be very happy to share these preliminary observations and explore them further.

AuthorsOpenReview ↗

Response to Reviewer hucG

Question 2: Experiments on larger instances. For a theoretical paper, the current experiments provide appropriate supporting evidence for the theoretical results. Additional experiments on larger instances, if feasible, would further strengthen this evidence. Could the authors provide runtime results for larger values of nn than 20, initially keeping the other parameters fixed? If such tests are computationally impractical, explaining the main bottlenecks would also help readers understand the computational scope of the method.

Response: Thank you for this constructive suggestion. We have extended the runtime experiment to four larger sizes (n=40,60,80,100n=40,60,80,100), while keeping k=3k=3, z=0z=0, and ε=λ=1\varepsilon=\lambda=1 fixed. We use the same complete implementation as in the original experiment, enumerating all radius profiles and running Algorithm 1 for each one.

At each new size, we draw two subsamples from each of the three datasets (Iris, Wine, and Breast Cancer Wisconsin Diagnostic), following the original preprocessing and seed rule. We have also rerun the six original n=20n=20 instances on the same machine to obtain a directly comparable baseline. The results are reported in Appendix F, Table 2.

nnMedian profile visitsMedian time (s)Max time (s)Max service stretch
2065,1712.682.771.658
40267,54119.9623.511.355
60607,11183.0287.761.467
801,083,881197.87201.851.324
1001,697,851376.91383.561.933

The median full-search time increases from 2.68 seconds at n=20n=20 to 376.91 seconds (6.28 minutes) at n=100n=100. The main computational bottlenecks are the growth in the number of enumerated radius profiles and the work performed within each profile. Each distinct positive pairwise distance contributes 73=3437^3=343 profiles. Within each profile, Algorithm 1 scans the remaining points to select pivots and construct capture sets. The median amortized time per profile visit increases from 41 microseconds at n=20n=20 to 225 microseconds at n=100n=100.

The full search completes successfully on all 24 larger instances, returning three centers and no outliers in every run. The experiments also show a maximum observed service stretch of 1.933, consistent with the theoretical bound of 2.

We thank the reviewer again for encouraging this addition, which helps clarify the computational scope of our algorithm.

Question 3: Potential applications. Could the authors describe a concrete application in which minimizing the sum of cluster radii and imposing individualized bounds on actual assignment distances are jointly meaningful? Although an immediate application is not necessary for the theoretical contribution, a plausible scenario would strengthen the practical motivation and help readers understand where the distinction between nearby centers and designated service matters.

Response: Thank you for this helpful suggestion. A plausible application is planning service areas for rural primary-care clinics that provide periodic community outreach, such as vaccination services. WHO's immunization microplanning guidelines (2009) explicitly discuss health-facility catchment areas, village-to-facility distances, and fixed, outreach, and mobile service sessions. Liu et al. (2025) also study village-to-clinic service allocation under clinic service-radius constraints.

In this setting, each clinic is located at one of the villages it serves, corresponding to a cluster center in our MSR model. Each village is assigned to a responsible clinic, and each clinic's radius is the distance to its farthest assigned village. With a fixed number of clinics, the sum of these radii measures the combined maximum outreach distances maintained across the clinics. Minimizing this sum seeks to reduce the aggregate geographic service burden. This is a service-range planning objective rather than total transportation cost, which also depends on visit frequency.

However, minimizing the sum of cluster radii alone does not guarantee appropriate service for every village. A village may be assigned to a distant clinic whose radius is already large, even when a closer clinic exists, because such an assignment may incur no additional radius cost. Reassigning it to the closer clinic may increase the total cost. Therefore, individualized bounds on actual assignment distances, such as those based on neighborhood radii, should be enforced for each village's designated clinic, rather than merely requiring a nearby clinic to exist. This illustrates why minimizing the sum of cluster radii and enforcing service-aware individual fairness are jointly meaningful.

We have added this example to the Introduction to clarify the practical motivation and the distinction between nearby centers and designated service. Thank you for this helpful suggestion.

Reviewer_hucGOpenReview ↗

Thank you for the thoughtful response.

Thank you for your thoughtful and detailed response. It addresses most of my questions. The additional experiments suggest that the current implementation may still face computational bottlenecks in large-scale deployment, but this limitation does not diminish the paper’s theoretical contribution. I will therefore maintain my rating and continue to support acceptance.

Reviewer_JLoiOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies individually fair minimum-sum-of-radii (MSR) clustering problem. Unlike the previous work, this paper studies service-aware solution, where every retained points's assigned center meets its service bound. They propose an algorithm that achieves (1) 2+ϵ2+\epsilon approximation ratio; (2) service ratio of 22; (3) at most kk centers and zz outliers. The time complexity is (k/ϵ)O(k)(k+1)k+znO(1)(k/\epsilon)^{O(k)} (k+1)^{k+z}n^{O(1)}, so this is a FPT (of kk, zz and ϵ\epsilon) algorithm.

Critical strengths
  1. The model is novel. Previous work related to individually fair clustering defines fairness through the center set, while previous fair MSR work focuses on groups constraints. such as color composition. This paper, as claimed by authors, is the first paper to combine individually fairness with MSR.

  2. The theoretical contribution is new and solid.

Critical weaknesses
  1. The algorithm combines many of known techniques. Processing points in increasing priority and capturing everything within 2λρ(x)2\lambda\rho(x) of the pivot is essentially the greedy strategy for priority (non-uniform) kk-center (Bajpai et al., 2021). The bound λρ(p)+λρ(x)≤2λρ(x)\lambda\rho(p)+\lambda\rho(x)\le 2\lambda\rho(x) is the standard argument there. Radius guessing with a factor-2 recentering is standard in FPT MSR (Chen et al. 2024; Bandyapadhyay & Chen 2025).

  2. The overall time complexity has exponential dependence on kk and zz. The fully polynomial-time approximation is not discussed.

Questions for authors
  1. How does Algorithm 1 differ from the priority kk-center greedy combined with radius-profile guessing?

  2. Can the (k+1)z(k+1)^{z} factor be removed, i.e., is the problem FPT in kk alone for fixed ϵ\epsilon?

3 comments
AuthorsOpenReview ↗

Response to Reviewer JLoi

We sincerely thank the reviewer for recognizing the novelty of our model and the strength of our theoretical contributions, as well as for the constructive feedback that helps us further strengthen our theoretical analysis. We address these concerns below.

Weakness 1: The algorithm combines many of known techniques. Processing points in increasing priority and capturing everything within 2λρ(x)2\lambda\rho(x) of the pivot is essentially the greedy strategy for priority (non-uniform) kk-center (Bajpai et al., 2021). The bound λρ(p)+λρ(x)≤2λρ(x)\lambda\rho(p)+\lambda\rho(x)\leq 2\lambda\rho(x) is the standard argument there. Radius guessing with a factor-2 recentering is standard in FPT MSR (Chen et al., 2024; Bandyapadhyay & Chen, 2025).

Response: Thank you for highlighting these connections. We agree that minimum-priority greedy selection (Bajpai et al., 2021), radius-profile guessing, and factor-two recentering (Chen et al., 2024; Bandyapadhyay & Chen, 2025) are known techniques. Our contribution is not the individual primitives, but establishing their simultaneous guarantees for service-aware MSR, where existing guarantees do not directly transfer. Specifically, priority kk-center does not control the MSR cost of actual assignments, as demonstrated by the Θ(k)\Theta(k) gap in Lemma 4. Moreover, designated service is non-mergeable (Lemma 5), preventing direct application of existing mergeable-constraint frameworks. Lemmas 7–10 establish that combining priority-based capture with radius constraints preserves complete residual-cluster capture, a consistent search path despite over-capture, and cost and budget control. This yields simultaneous (2+ε)(2+\varepsilon)-cost, factor-2 assigned-service, and budget-preserving guarantees (Theorem 11). We will clarify the connections to prior techniques and the precise scope of our contribution.

Weakness 2: The overall time complexity has exponential dependence on kk and zz. The fully polynomial-time approximation is not discussed.

Response: Thank you for raising this concern. Motivated by your constructive feedback, we have revisited the dependence on kk and zz and refined the running-time analysis of Algorithm 1, obtaining a substantially improved running-time bound. We have also established a new complexity lower bound that clarifies the limitations of further improvements under the current guarantees. These results provide a more complete understanding of the algorithm's efficiency and its theoretical limits. We present the detailed analysis in our response to Question 2.

We regard exploring fully polynomial-time approximation for service-aware MSR as a challenging and interesting direction for future work. We believe that relaxing service guarantees, allowing modest budget augmentation, or introducing additional structural assumptions may provide promising opportunities for developing polynomial-time algorithms. In future work, we aim to further investigate the trade-offs among approximation quality, service fairness, and computational efficiency, with the goal of designing polynomial-time approximation algorithms for service-aware MSR. We sincerely appreciate the reviewer's valuable suggestion.

Question 1: How does Algorithm 1 differ from the priority kk-center greedy combined with radius-profile guessing?

Response: Thank you for this question. Algorithm 1 builds on priority kk-center greedy and radius-profile guessing, rather than introducing a fundamentally different greedy strategy. The key distinction lies in the problem-specific analysis and guarantees. For service-aware MSR, the existing techniques do not directly establish simultaneous control of the assignment-dependent MSR cost and the assigned-center distance of every retained point. Our analysis of Algorithm 1 (Lemmas 7–10) proves that the combined search admits a consistent path despite over-capture, while preserving cost and budget control. This leads to the joint cost, assigned-service, and budget guarantees in Theorem 11, which are not established by the existing techniques alone.

AuthorsOpenReview ↗

Response to Reviewer JLoi

Question 2: Can the (k+1)z(k+1)^z factor be removed, i.e., is the problem FPT in kk alone for fixed ε\varepsilon?

Response: Thank you for this insightful question. Motivated by your feedback, we have substantially improved the running-time analysis of Algorithm 1. Instead of using the worst-case branching factor, we count the search paths directly. Since each radius label is used at most once and at most zz outlier branches are taken, Appendix H.1 bounds the number of leaves per radius profile by k!(k+zk)k!\binom{k+z}{k}. This improves the running time from (k/ε)O(k)(k+1)k+znO(1)(k/\varepsilon)^{O(k)}(k+1)^{k+z}n^{O(1)} to (k/ε)O(k)(z+1)knO(1)(k/\varepsilon)^{O(k)}(z+1)^k n^{O(1)} (Theorem 11). Thus, the dependence on zz is no longer exponential but polynomial for fixed kk.

More importantly, we have established a new parameterized complexity lower bound for algorithms preserving both budgets and guaranteeing service stretch below 3. Theorem 21 (Appendix H.2) proves that, for arbitrary priorities, any deterministic f(k)nO(1)f(k)n^{O(1)}-time algorithm preserving both budgets and guaranteeing service stretch τ<3\tau<3 whenever exact 1-service is feasible would imply FPT=W[2]\mathrm{FPT}=\mathrm{W}[2]. The proof uses a parameter-preserving reduction from Dominating Set and holds even with strictly positive priorities and unrestricted MSR cost. Since our service factor is 2, this lower bound applies directly to our guarantees. Therefore, a deterministic FPT algorithm parameterized by kk alone is ruled out under our current service and budget guarantees unless FPT=W[2]\mathrm{FPT}=\mathrm{W}[2].

We acknowledge that this lower bound does not rule out kk-only FPT algorithms under relaxed service guarantees or budget augmentation, such as allowing O(k)O(k) centers beyond the original budget. We believe that exploring these possibilities represents a promising and valuable direction for future research. We sincerely appreciate the reviewer's insightful question.

Thanks for the detailed response. I will remain my positive rating for this paper.

Comments on the paper

1 comment
AuthorsOpenReview ↗

To all the reviewers: Summary of Changes

We sincerely thank all the reviewers for their insightful comments and constructive feedback. In response to the reviewers' suggestions, we have revised and extended the paper, with all revisions highlighted in blue. The main changes are summarized as follows:

  • Added a practical motivation and clarified the distinction between selected-set fairness and service fairness in the Introduction.
  • Strengthened the theoretical analysis and clarified the key mechanisms of the proposed minimum-priority capture algorithm.
  • Refined the search-tree analysis and improved the running-time bound to (k/ε)O(k)(z+1)knO(1)(k/\varepsilon)^{O(k)}(z+1)^k n^{O(1)}.
  • Established a new parameterized hardness result showing that, unless FPT=W[2]\mathrm{FPT}=\mathrm{W}[2], deterministic algorithms parameterized only by kk cannot guarantee service stretch below 3 while preserving both budgets (Appendix H.2).
  • Conducted additional experiments on larger instances with up to n=100n=100, evaluating running time, profile visits, and service-fairness performance.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.