Linear Programming based Approximation to Individually Fair k-Clustering with Outliers

Anirban Dasgupta; Binita Maity; Shrutimoy Das

REVIEW 3 major objections 5 minor 24 references

Linear Programming based Approximation to Individually Fair k-Clustering with Outliers

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A linear program that marks outlier candidates and then rounds centers gives constant-factor approximation guarantees for individually fair k-means and k-median clustering with outliers.

desk verdict The LP is a genuine first step, but the missing bound on detected outliers breaks the claimed approximation. read the letter →

arxiv 2412.10923 v1 pith:QVTGYLYW submitted 2024-12-14 cs.LG cs.DSstat.ML

Binita Maity , Shrutimoy Das , Anirban Dasgupta This is my paper · ORCID

classification cs.LGcs.DSstat.ML MSC 68W2590C05

keywords individuallyfairclusteringoutliersk-meansk-medianlinearprogrammingapproximationalgorithm

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that individually fair k-clustering can be solved in the presence of outliers by folding outlier detection into a linear program. The algorithm solves the LP, rounds the outlier variables to remove marked points, and then applies a known fair-rounding routine to the remaining points. If correct, the result is that every inlier has a center within 16 times its fair radius, and the clustering cost is within a factor of 12 for k-means or 24 for k-median of the optimal cost that may discard up to m outliers. This is the first work to bring individual fairness to k-means clustering with outliers. The authors also report experiments on three standard datasets, where the number of points marked as outliers stayed at most three times the injected outlier budget.

What carries the argument

The argument rests on a linear program that couples three families of variables: assignment variables $x_{vu}$, center-opening variables $y_u$, and outlier-indicator variables $z_v$. Constraints limit centers to $k$, outliers to $m$, require every non-outlier to be fully assigned within its fair radius ($LP6$ with $\alpha = 1$), and forbid an outlier from serving as a center. The OutRound algorithm then rounds $z$ by a zero threshold, and for each outlier that was a center, transfers its assignment mass to the nearest non-outlier point. The load-bearing inequality is Lemma 1: the triangle inequality gives $d(v,u') \leq 2d(v,u_{OT}) \leq 2r(v)$ for every point $v$ formerly assigned to an outlier-center, and summing these reassignment costs with the original costs yields $LP_{\alpha=2}(x',y') \leq 3\,LP_{\alpha=1}(x^*,y^*,z^*)$. This factor-3 cost bound is what converts FairRound's approximation guarantees into the 12/24 cost and 16 radius claims.

What would settle it

On a synthetic instance with a uniquely optimal m-outlier clustering, run the LP and OutRound with threshold 0 and count points with z_v > 0; if any instance yields more than m, the output violates the feasibility constraint of Definition 3 and the claimed 12/24 cost approximation against the m-outlier optimum is not established.

Watch

Extended reading notes

Core claim

The paper's central discovery is that outlier identification can be folded into the individual-fairness LP itself. The LP uses a variable $z_v$ for each point, with $z_v = 1$ interpreted as 'v is an outlier'; constraints limit the number of marked points to $m$ and forbid a marked point from being a center. After solving the LP, the algorithm OutRound thresholds $z$ at $\tau = 0$, removes every point with $z_v > 0$, and for any removed point that was acting as a center reassigns its assigned mass to the nearest remaining point. The key bound, Theorem 1, shows that this reassignment increases the LP cost by at most a factor of 3 while degrading the fair-radius constraint from $\alpha = 1$ to $\alpha = 2$. Combined with the FairRound algorithm of [23], which gives a 4-approximation for k-means and an 8-approximation for k-median, this yields a 12-approximation to the optimal k-means cost and a 24-approximation to the optimal k-median cost, and a 16-approximation to the fair radius for inliers.

Load-bearing premise

The load-bearing premise is that the thresholded outlier set never exceeds the budget m, a fact the paper does not prove and its experiments show can fail by a factor of three.

Editorial extensions

If this is right

If the central claim is correct, any dataset with up to m outliers can be clustered so that every inlier has a center within 16 times its fair radius, with cost at most 12 (k-means) or 24 (k-median) times the optimal that is allowed to discard m points.
The outlier-marking LP reduces to the existing no-outlier fair-clustering LP when m = 0, so the algorithm is a strict generalization of previous individually fair clustering.
The factor-3 cost bound is independent of the distance exponent p, so the same outlier-detection and rounding scheme gives constant-factor guarantees for both k-median (p=1) and k-means (p=2).
Because the method only requires solving one linear program and then rounding, it provides a concrete polynomial-time recipe for fair clustering with outliers that works with standard LP solvers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The proof of Theorem 1 does not use the constraint that at most m points be marked as outliers, so the factor-3 cost bound holds for whatever set OutRound outputs; the unresolved question is whether the number of marked points can be bounded by a function of m, since otherwise the output may violate the feasibility condition of Definition 3.
The experiments suggest that a positive threshold $\tau$ could trade a slightly larger cost or fairness slack for fewer detected outliers, and a provable trade-off between $\tau$ and the number of marked points is a natural next step that the paper leaves open.
OutRound moves all assignment mass from an outlier-center to the single nearest remaining point; splitting that mass among several nearby centers would likely reduce the cost blow-up below the proven factor of 3, though the triangle-inequality argument would need to be reworked.
The computational bottleneck is the large LP, and the experiments restrict attention to 1000-point samples; a coreset or dimension-reduction approach tailored to this LP with outlier variables could let the method scale to full datasets.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this is the first LP for individually fair k-means/k-median with outliers, and the cost-transfer argument (LP' ≤ 3LP*) is clean for the inliers. But the paper's headline guarantee doesn't hold as stated, because OutRound with τ=0 can mark more than m points as outliers, and the problem definition (Def 3) caps the outlier set at m. The authors acknowledge this in Section 5 and their own Table 2 shows up to 3m detections. When that happens, the output is infeasible, and comparing its inlier cost to an optimal solution with m outliers is not valid.

What's new and good: the LP with z_v variables, the OutRound reassignment for centers that are also outliers, and the use of the prior FairRound result are all sensible. The proof of Lemma 1 is a straightforward triangle inequality and the 3-factor bound for the LP cost holds for the inlier portion. The paper is also honest: it states plainly that no outlier-count bound is shown.

Soft spots, in order of importance. First, the missing |Z'| bound is load-bearing, not a technicality. An optimal LP solution can spread z* fractionally over many points (e.g., z*_v = m/n for all v), so thresholding at zero marks everything as an outlier. The paper tries to patch this empirically, but an example like that kills the guarantee. Second, Theorem 1's statement is ambiguous: LPα=2(x',y',z') includes the outlier assignments, yet the proof only bounds the inlier cost (X\X_OUT). If the outlier set is too large, the RHS comparison to OPT doesn't follow. Third, the evaluation is light: single runs, no error bars, and Figure 2 contains a local file path artifact. Those are minor relative to the main gap.

Bottom line: it's a promising start on an open problem, and the LP formulation may be repairable—either by proving a bound on the number of positive z*_v's under some separation condition, or by explicitly relaxing the problem to allow up to c*m outliers. As it stands, the central claim is not supported. I'd still send it to a serious referee if the venue tolerates substantive revision, because the idea and the clean inlier cost bound deserve scrutiny and the gap is clearly identified by the authors themselves.

Recommendation: engage with it if you work on fair clustering; otherwise wait for a revision that fixes the feasibility issue.

Referee Report

3 major / 5 minor

Summary. The paper studies individually fair k-clustering (k-means and k-median) in the presence of up to m outliers. It introduces a linear program with fractional center, assignment, and outlier variables, solves it, rounds the outlier variables by thresholding at τ=0 (Algorithm 2, OutRound), removes the detected outliers, and applies the FairRound algorithm of [23] to the remaining points. The main theoretical claim is that this yields a 12-approximation for k-means and a 24-approximation for k-median with respect to the optimal cost for the m-outlier problem, and a 16-approximation to the fair radius for inliers. Experiments on three UCI datasets report clustering costs and fairness radius values. The paper explicitly states that no bound is shown on the number of detected outliers (Section 5).

Significance. If the central claims were correct, this would be the first LP-based constant-factor bicriteria approximation for individually fair k-clustering with outliers, extending the prior work of Negahbani and Chakrabarty. The idea of using an LP to identify outliers and then applying a known rounding algorithm is natural, and the paper is transparent about its main limitation. However, because the rounding step can mark more than m points as outliers, the output is not a feasible solution to the (α,k,m)-fair clustering problem of Definition 3, and the claimed cost and fairness guarantees relative to an optimum that excludes at most m outliers are not established. This is a load-bearing gap; the paper should be substantially revised before its main theorem can be accepted.

major comments (3)

[§5, Theorem 1 and Algorithm 2] The rounding rule z'_v = 1 iff z*_v > 0 (Algorithm 2, line 7, with τ=0) can mark more than m points as outliers, because constraint (LP2) only bounds the sum of the fractional outlier values, not the number of positive entries. An LP solution with z*_v = m/n for every v would make all n points labeled outliers. The output is then not a feasible (α,k,m)-fair clustering as defined in Definition 3, and the claimed 12x/24x cost approximation and 16x fair-radius guarantee with respect to an optimum that excludes at most m outliers are not established. The paper explicitly concedes this in Section 5 ('we do not show any bounds for the number of outliers detected') and in the future-work paragraph, and Table 2 reports up to 3m detected outliers for m=10. To repair this, the algorithm should select at most m outliers (e.g., the m largest z* values), which would preserve the inequalities in the proof of Theorem 1; the theorem and experiments must then be restated for the modified procedure.
[Algorithm 2, line 15] The reassignment loop 'for ∀v ∈ X such that x_vu_OT≠0 do x'_vu' ← x'_vu' + x_vu_OT' runs over all v, including points that were marked as outliers in lines 7-8 and whose x' entries were zeroed in line 8. This gives outlier points nonzero assignment values, contradicting their exclusion and making the subsequent call to FairRound on X_in inconsistent with x'. The proof of Theorem 1 sums only over v∈X\X_OT, so the pseudocode needs to be changed to restrict the loop to v not in outlier_indices.
[§5, Theorem 1 statement and Eq. (11)-(12)] The statement 'LPα=2(x′, y′, z′) ≤ 3LPα=1(x∗, y∗, z∗)' is imprecise: the LP cost does not depend on z, and the proof actually bounds the cost on the inlier set X\X_OT. More importantly, the chain in Eq. (11)-(12) concludes FR(x',y') ≤ 12 OPT2 without establishing that the algorithm's outlier set has size at most m, so the comparison to OPT2, the optimal cost for the m-outlier problem, is not meaningful. The paper should state the result as an explicit bicriteria approximation (allowing βm outliers) or prove a bound on the number of detected outliers.

minor comments (5)

[Algorithm 2, line 7] The expression '1[z*[v] > τ]]' has an extra closing bracket; it should read '1[z*[v] > τ]'.
[Definition 3] The phrase 'Z is denotes as outliers' is ungrammatical; it should be 'Z is the set of outliers' or 'Z denotes the outliers'.
[Table 2 and Tables 3-4] Table 2 shows that IFXO can detect up to 3m outliers when m=10, but the cost comparisons in Tables 3 and 4 are computed after removing those detected points. Since the baseline iForest removes exactly 10 outliers, the comparisons are not on equal footing and should be discussed or adjusted.
[§5, notation] The notation OPT2 and OPT1 is introduced only after Eq. (12); these should be defined before their first use in the text.
[§5, sentence after Theorem 1 proof sketch] The sentence 'This ensures that the xvu values always decrease whenever a point v is marked as an outlier' is unclear; for τ=0 the x values of marked outliers are set to zero, but the statement should be phrased more precisely.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the approximation bounds follow from the LP, triangle inequality, and an external prior rounding result.

full rationale

Walking the derivation chain, the claimed factors do not reduce to the paper's inputs. Theorem 1's factor of 3 is proved in Equations (7)-(10) by comparing each reassigned center to the original LP center via triangle inequality; no constant is fitted and no quantity is defined in terms of the quantity it claims to bound. The 12x/24x factors multiply this 3 by the 4/8 approximation of FairRound from [23], an external prior work by Negahbani and Chakrabarty, not by the present authors. The 16x fair-radius factor combines Lemma 1's factor of 2 with the external 8x fair-radius result from [23]. These are independent benchmarks, not self-citations. The only self-citation is [8] (Chhaya, Dasgupta, et al.) in the introduction as a scalable method for individually fair clustering; it is contextual and not load-bearing for any proof. The paper explicitly concedes in Section 5, 'we do not show any bounds for the number of outliers detected,' and Table 2 reports up to 3m detected outliers for m=10; this is a genuine feasibility/correctness gap against Definition 3, but it is not a circular derivation. Therefore no circular step is present, and the derivation is self-contained modulo the external FairRound result.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the metric triangle inequality for the distance function, the external FairRound guarantees of the cited work, and the standard LP relaxation argument. No data-fitted constants are used; the only hand-chosen quantity is the outlier threshold tau=0, whose effect on the outlier budget is unproven.

free parameters (1)

Outlier threshold tau = 0
z'_v = 1 iff z*_v > tau. The proof of Theorem 1 requires tau=0; the paper sets tau=0 based on the empirical observation that the LP's nonzero z* count is at most 3m, but provides no theoretical bound.

assumptions (4)

domain assumption The metric distance function d satisfies the triangle inequality.
Used in Lemma 1 and Theorem 1 to bound d(v,u') ≤ 2 d(v,u_OUT); the clustering problem is assumed metric in Definition 3 and the LP setup.
domain assumption FairRound from the cited work returns centers satisfying the stated 4-approximation (k-means), 8-approximation (k-median), and 8-approximation fair radius guarantees with respect to the LP solution it is given.
Invoked in Section 5 to convert LP' cost into final center cost; the present paper does not re-derive this.
standard math The LP relaxation is a valid relaxation of the integer fair-clustering-with-outliers problem, so an optimal integer solution maps to a feasible LP solution with the same cost.
Implicit in the inequality LP* ≤ OPT in Theorem 1; standard LP relaxation argument.
domain assumption The fair radius r(v) is defined with respect to the original full dataset X, including outliers, and remains fixed when the inlier set is reduced.
Definition 1 and the LP constraints use r(v) computed on X; the algorithm computes centers on X_in but does not recompute r(v), which the problem definition requires.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Linear Programming based Approximation to Individually Fair k-Clustering with Outliers." pith.science (2026). https://pith.science/paper/QVTGYLYW

@misc{pith2026241210923,
  author       = {Pith},
  title        = {Pith review of: Linear Programming based Approximation to Individually Fair k-Clustering with Outliers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QVTGYLYW}},
  note         = {Machine review of arXiv:2412.10923}
}

abstract

Individual fairness guarantees are often desirable properties to have, but they become hard to formalize when the dataset contains outliers. Here, we investigate the problem of developing an individually fair $k$-means clustering algorithm for datasets that contain outliers. That is, given $n$ points and $k$ centers, we want that for each point which is not an outlier, there must be a center within the $\frac{n}{k}$ nearest neighbours of the given point. While a few of the recent works have looked into individually fair clustering, this is the first work that explores this problem in the presence of outliers for $k$-means clustering. For this purpose, we define and solve a linear program (LP) that helps us identify the outliers. We exclude these outliers from the dataset and apply a rounding algorithm that computes the $k$ centers, such that the fairness constraint of the remaining points is satisfied. We also provide theoretical guarantees that our method leads to a guaranteed approximation of the fair radius as well as the clustering cost. We also demonstrate our techniques empirically on real-world datasets.

Figures

Figures reproduced from arXiv: 2412.10923 by the authors.

**Figure 1.** Individually fair 2- clustering in the presence of an outlier. It is easy to see that the presence of outliers can significantly alter the fair clustering objective. We give an example in [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

**Figure 2.** Maximum Fairness Radius for the Bank dataset for different number of clusters. We tested our proposed method on a variety of datasets and report the results. We experimented on the following datasets from UCI machine Learning Repository [12]. These datasets are standard benchmarks for fair kclustering [1, 4, 7, 9, 16]. – Bank: This is Portuguese Bank dataset[22]. There are three features age, balance and duration-… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 22 canonical work pages

[23]

In: Advances in Neural Information Processing Systems (2021)

Negahbani, M., Chakrabarty, D.: Better algorithms for individually fair $k$- clustering. In: Advances in Neural Information Processing Systems (2021)

work page 2021
[1]

Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., Wagner, T.: Scalable fair clustering (2019)

work page 2019
[2]

ArXiv (2024)

Bateni, M., Cohen-Addad, V., Epasto, A., Lattanzi, S.: A scalable algorithm for individually fair k-means clustering. ArXiv (2024)

work page 2024
[3]

Becker, B., Kohavi, R.: Adult (1996)

work page 1996
[4]

Bera, S.K., Chakrabarty, D., Flores, N.J., Negahbani, M.: Fair algorithms for clustering (2019)

work page 2019
[5]

In: ACM-SIAM Symposium on Dis- crete Algorithms (2001)

Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: ACM-SIAM Symposium on Dis- crete Algorithms (2001)

work page 2001
[6]

In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Chen, K.: A constant factor approximation algorithm for k-median clus- tering with outliers. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’08 (2008)

work page 2008
[7]

Chen, X., Fain, B., Lyu, L., Munagala, K.: Proportionally fair clustering (2020)

work page 2020

Show all 24 references

[8]

In: Proceedings of The 25th Inter- national Conference on Artificial Intelligence and Statistics

Chhaya, R., Dasgupta, A., Choudhari, J., Shit, S.: On coresets for fair re- gression and individually fair clustering. In: Proceedings of The 25th Inter- national Conference on Artificial Intelligence and Statistics. pp. 9603–9625 (2022)

2022
[9]

CoRR (2018)

Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. CoRR (2018)

2018
[10]

1: User’s manual for cplex

Cplex, I.I.: V12. 1: User’s manual for cplex. International Business Machines Corporation (2009) 12 Binita Maity ∗, Shrutimoy Das∗, and Anirban Dasgupta

2009
[11]

In: Proceed- ings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI) (2020)

Deshpande, A., Kacham, P., Pratap, R.: Robustk-means++. In: Proceed- ings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI) (2020)

2020
[12]

Dheeru, D., Taniskidou, E.K.: machine learning repository, 2017 (2017)

2017
[13]

Gupta, S., Kumar, R., Lu, K., Moseley, B., Vassilvitskii, S.: Local search methods for k-means with outliers. Proc. VLDB Endow. (2017)

2017
[14]

Han, L., Xu, D., Xu, Y., Yang, P.: Approximation algorithms for the indi- vidually fair k-center with outliers. J. of Global Optimization (2022)

2022
[15]

In: Forty-first International Conference on Machine Learning (2024)

Huang, J., Feng, Q., Huang, Z., Xu, J., Wang, J.: Near-linear time approx- imation algorithms for k-means with outliers. In: Forty-first International Conference on Machine Learning (2024)

2024
[16]

Huang,L.,Jiang,S.H.C.,Vishnoi,N.K.:Coresetsforclusteringwithfairness constraints (2019)

2019
[17]

CoRR (2020)

Im, S., Qaem, M.M., Moseley, B., Sun, X., Zhou, R.: Fast noise removal for k-means clustering. CoRR (2020)

2020
[18]

CoRRabs/1908.09041 (2019)

Jung, C., Kannan, S., Lutz, N.: A center in your neighborhood: Fairness in facility location. CoRRabs/1908.09041 (2019)

2019 arXiv
[19]

Krishnaswamy, R., Li, S., Sandeep, S.: Constant approximation for k- median and k-means with outliers via iterative rounding (2018)

2018
[20]

In: 2008 Eighth IEEE International Conference on Data Mining

Liu, F.T., Ting, K.M., Zhou, Z.H.: Isolation forest. In: 2008 Eighth IEEE International Conference on Data Mining. pp. 413–422 (2008). https://doi. org/10.1109/ICDM.2008.17

2008 doi
[21]

In: Proceed- ings of the 37th International Conference on Machine Learning (2020)

Mahabadi, S., Vakilian, A.: Individual fairness for k-clustering. In: Proceed- ings of the 37th International Conference on Machine Learning (2020)

2020
[22]

UCI Machine Learning Repository (2012)

Moro: Bank Marketing. UCI Machine Learning Repository (2012)

2012
[24]

In: Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (2022)

Vakilian, A., Yalciner, M.: Improved approximation algorithms for individ- ually fair clustering. In: Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (2022)

2022

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [23]

In: Advances in Neural Information Processing Systems (2021)

Negahbani, M., Chakrabarty, D.: Better algorithms for individually fair $k$- clustering. In: Advances in Neural Information Processing Systems (2021)

work page 2021

[2] [1]

Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., Wagner, T.: Scalable fair clustering (2019)

work page 2019

[3] [2]

ArXiv (2024)

Bateni, M., Cohen-Addad, V., Epasto, A., Lattanzi, S.: A scalable algorithm for individually fair k-means clustering. ArXiv (2024)

work page 2024

[4] [3]

Becker, B., Kohavi, R.: Adult (1996)

work page 1996

[5] [4]

Bera, S.K., Chakrabarty, D., Flores, N.J., Negahbani, M.: Fair algorithms for clustering (2019)

work page 2019

[6] [5]

In: ACM-SIAM Symposium on Dis- crete Algorithms (2001)

Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: ACM-SIAM Symposium on Dis- crete Algorithms (2001)

work page 2001

[7] [6]

In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Chen, K.: A constant factor approximation algorithm for k-median clus- tering with outliers. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’08 (2008)

work page 2008

[8] [7]

Chen, X., Fain, B., Lyu, L., Munagala, K.: Proportionally fair clustering (2020)

work page 2020