Pith. sign in

REVIEW 2 major objections 5 minor 30 references

A scalable linear programming-based framework for data clustering

T0 review · 2 major / 5 minor · reviewed 2026-07-10 · grok-4.5

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

Pith's one-line read A single linear-programming cutting-plane method solves fair K-means and spectral clustering to near-optimality on instances with thousands of points.

desk verdict Clean, useful extension of a strong K-means LP to fair and spectral clustering, with solid math and large-scale evidence of near-tightness up to n=3000. read the letter →

arxiv 2607.06709 v1 pith:MEKFWKLT submitted 2026-07-07 math.OC

Aida Khajavirad , Huanwen Shen , Yakun Wang This is my paper · ORCID
classification math.OC MSC 90C0590C5768T0562H30
keywords fairK-meansclusteringspectrallinearprogrammingrelaxationcutting-planealgorithmpartitionmatrixratio-cutgroupfairness
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 shows that two widely used clustering tasks—fair K-means and spectral (ratio-cut) clustering—can be handled by the same scalable linear-programming cutting-plane engine previously developed for ordinary K-means. Fairness notions such as proportional representation and ratio fairness translate into a linear number of linear inequalities on the partition matrix, while spectral clustering is obtained simply by replacing the squared-distance objective with the graph Laplacian. Customized initialization and rounding (fair Lloyd and spectral embedding, respectively) supply good feasible solutions. On real-world data sets with up to a few thousand points the method closes the gap to within 1 percent for roughly 90 percent of fair instances and 94 percent of spectral instances inside three hours, and frequently returns better clusterings than the popular fair-Lloyd and spectral heuristics. The practical message is that a single, carefully engineered LP framework can deliver certified near-optimal solutions for several important clustering models that were previously treated only heuristically.

What carries the argument

The partition-matrix LP relaxation (LPK_t) whose exponential family of inequalities is separated on the fly by a greedy heuristic; fairness is encoded by a linear number of additional linear inequalities on the same matrix, while spectral clustering uses the identical feasible region with Laplacian objective coefficients.

What would settle it

A family of real or synthetic instances with n ≤ 3000 on which the cutting-plane algorithm, after exhausting the time limit and all available cuts, still reports a relative gap larger than a few percent while a known better fair or spectral clustering exists.

Watch

Extended reading notes

Core claim

Widely used group-fairness constraints on K-means and the minimum-ratio-cut formulation of spectral clustering both admit strong linear-programming relaxations that fit inside the same cutting-plane architecture; on real instances with n ≤ 3000 these relaxations are tight enough that the algorithm routinely reaches a 1 percent optimality gap within a few hours and often improves on standard heuristics.

Load-bearing premise

The incomplete greedy separator for the exponential inequalities, together with the problem-specific rounding steps, is assumed to be strong enough to drive the gap below one percent on the chosen real-world data sets.

Editorial extensions

If this is right

  • Practitioners can obtain certified near-optimal fair clusterings for data sets of a few thousand points without having to rely solely on fair-Lloyd heuristics.
  • The same code base yields high-quality, gap-certified solutions for community detection via the ratio-cut objective.
  • Because fairness enters only as a linear number of linear inequalities, other linearizable fairness notions can be swapped in with essentially no redesign of the solver.
  • The observed near-tightness of the LP on real data suggests that further theoretical recovery guarantees for these particular fair and spectral LPs may be attainable.

Reading between the lines

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

  • If the same LP polytope remains strong under other linearizable side constraints (capacity, diversity, size bounds), a single cutting-plane engine could become a general-purpose exact clustering workhorse.
  • The frequent superiority over spectral heuristics on real networks hints that the ratio-cut LP may be recovering communities that eigenvector methods systematically miss.
  • Scaling the method beyond a few thousand points will likely require either a faster first-order LP solver or a more aggressive cut-management strategy that discards inactive inequalities earlier.
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.

Referee Report

2 major / 5 minor

Summary. The paper extends the cutting-plane LP framework of De Rosa et al. for K-means (partition-matrix formulation with the exponential family of inequalities (4)) to fair K-means and to spectral clustering via the minimum ratio-cut. Fairness notions (proportional representation / balance and τ-ratio) are encoded as a linear number of linear inequalities on the partition matrix (Propositions 1–2, inequalities (15) and (17)). The same LP skeleton is used for ratio-cut by substituting Laplacian entries for squared distances. Problem-specific initialization and rounding are supplied by a fair Lloyd heuristic (Algorithm 3, with assignment IPs (fairAssignI/II)) and by spectral embedding + Lloyd (Algorithms 5–6). Extensive experiments on UCI and SNAP instances (n≤3000 for fair, n≤1500 for spectral) report that ~90% (fair) and ~94% (spectral) of instances reach a 1% relative gap within three hours, and that the method improves on fair Lloyd / spectral heuristics on more than half the instances.

Significance. If the computational claims hold, the work supplies a practical, certifiably near-optimal LP pipeline for two widely used clustering paradigms that previously relied almost exclusively on heuristics or approximation algorithms. The fairness encodings are elementary but useful: they show that standard group-fairness constraints fit the partition-matrix polytope with only O(n|G|) inequalities, so the existing separator for (4) remains the bottleneck. Propositions 3–4 (total unimodularity of the τ-fair assignment LP and NP-hardness of the α-fair assignment IP via 3DM) cleanly justify the design of the fair Lloyd subroutine. The large, tabulated computational study (286 fair + 142 spectral instances, performance profiles, explicit comparison to unfair K-means and to popular heuristics) is a genuine contribution for the math.OC / computational optimization community and makes the near-tightness claim falsifiable on public data. Code and data are linked, which strengthens reproducibility.

major comments (2)
  1. The central claim of “remarkable strength” of the fair and spectral LPs (Abstract; §3.3, §4.2) rests on a non-exact greedy separator (Algorithm 1) whose completeness is not analyzed. While this is standard for cutting-plane papers and the reported gaps are concrete and reproducible, the manuscript should state more carefully that tightness is observed under this incomplete separator (and under the chosen p_init / t_max schedule), not proved. A short discussion of residual gap sources (separator incompleteness vs. genuine fractional vertices of the fair/spectral polytope) would make the claim more precise without changing the experimental conclusions.
  2. Table 2 / AS2 (n=3000) and several spectral instances with n=1500 hit the 3-hour limit with gaps still above 10^{-3} (occasionally ~10^{-2}). The abstract’s “90% … within 1%” statement is numerically correct but aggregates easy small-n instances with harder ones; a clearer breakdown by size (or a statement that the method is reliable primarily for n≲1000–2000 under the current GPU/first-order setup) would better calibrate the scalability claim.
minor comments (5)
  1. Notation: the same symbol X is used for the data set and for the partition matrix; a brief reminder at the start of §3.1 would help.
  2. In Proposition 4 the reduction constructs K=|T| centers and allows empty clusters; a one-sentence remark that empty clusters are admissible under (18) when the sum of z_ik is zero would avoid a possible reader objection.
  3. Figures 3–6 (Appendix) are useful but the golden-hexagon markers for t_max increases are hard to see in grayscale; consider a different marker or a vertical line.
  4. A few typos: “77% if the instances” (§1.2), “Adultdata set” spacing, and occasional missing spaces after periods in the tables.
  5. The paper cites the companion K-means LP work [8] heavily; a short paragraph contrasting what is inherited versus what is new (fairness inequalities, fair Lloyd, spectral objective + rounding) would help readers who have not read [8].

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: empirical LP cutting-plane results on fixed public data with declared parameters; prior self-citation is infrastructure only.

full rationale

This is a computational optimization paper whose central claims are observed performance numbers (90% of fair K-means instances with n≤3000 to ≤1% gap in ≤3 h; 94% of spectral instances; better solutions than heuristics on >56% of instances) on named UCI/SNAP data sets under fixed algorithmic knobs (p_init, t_max, ϵ_opt, ρ). Fairness encodings (Props. 1–2) are elementary linear rewritings of standard balance/τ-ratio constraints in the partition-matrix variables; the assignment polyhedra (Props. 3–4) are standard total-unimodularity / 3DM reductions. The LP relaxation itself is obtained by adjoining a linear number of inequalities to the authors’ prior K-means LP or by swapping objective coefficients for Laplacian entries; the cutting-plane engine (safe dual bounds, greedy separation of (4), GPU first-order solver) is reused infrastructure, not a derivation that forces the reported gaps. No parameter is fitted to a subset of the benchmark and then “predicted”; ρ and K are declared inputs. Self-citation of De Rosa et al. supplies the base algorithm and is not load-bearing for a uniqueness or tightness theorem that the present paper then re-uses as an external fact. Consequently the derivation chain contains no self-definitional step, no fitted-input-called-prediction, and no uniqueness imported from the authors. Score 0 is the honest finding.

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

Load-bearing content is mostly standard combinatorial optimization plus the authors’ prior LP for K-means. Free parameters are algorithmic and fairness knobs chosen for experiments, not fitted constants that define a physical law. No new physical entities; the partition-matrix and cut inequalities come from prior literature.

free parameters (3)
  • ρ (fairness tightness)
    Chosen in {0.99,0.9,0.8,0.7} to define α_g, β_g or τ_g; controls how strict fairness is and which instances are feasible. Not fitted to optimize a scientific constant, but free experimental choice that shapes reported balances and costs.
  • p_init, p_max, t_max schedule, ϵ_opt, T
    Cutting-plane and termination parameters (e.g. p_init=10^6 or 10^7, ϵ_opt=10^{-4}, T=10800s) chosen by the authors; they affect runtime and reported gaps without being derived from first principles.
  • K (number of clusters)
    User-chosen discrete parameter in {2..5} or {2..10}; standard for clustering but free relative to any data-generating model.
assumptions (4)
  • domain assumption Partition-matrix formulation of K-means / ratio-cut and the validity of inequalities (4) for the LP relaxation LPK_t
    Taken from De Rosa et al. and related LP/SDP clustering literature (§1–2); not re-proved here.
  • standard math Node-edge incidence matrices of bipartite graphs are totally unimodular (used for Prop. 3)
    Invoked via Conforti et al. Theorems 4.18 and 4.5 in the proof that the LP relaxation of fairAssignII is integral.
  • domain assumption Group fairness notions (balance, α/β proportional representation, τ-ratio) are the right constraints to encode disparate impact
    Adopted from fair-clustering literature [5,4,14]; the paper does not justify them philosophically, only that they become linear in X.
  • ad hoc to paper Greedy clique-style separation (Algorithm 1) is an adequate practical separator for (4)
    Explicitly non-exact; efficiency and near-tightness claims rest on its empirical success on the tested instances.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A scalable linear programming-based framework for data clustering." pith.science (2026). https://pith.science/paper/MEKFWKLT

@misc{pith2026260706709,
  author       = {Pith},
  title        = {Pith review of: A scalable linear programming-based framework for data clustering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MEKFWKLT}},
  note         = {Machine review of arXiv:2607.06709}
}
abstract

We extend the linear programming-based algorithm of De Rosa et al~\cite{derKhaWan24} for K-means clustering to two important clustering paradigms: fair K-means clustering and spectral clustering. For fair K-means clustering, we show that widely used notions of group fairness can be incorporated into the partition-matrix formulation of K-means clustering through a linear number of linear inequalities. For spectral clustering, we consider a linear programming relaxation of the minimum ratio-cut problem that fits naturally within the same framework. We complement these formulations with problem-specific initialization and rounding procedures and evaluate the resulting algorithms on a large collection of real-world data sets. Denoting by $n$ the number of data points, our computational results demonstrate that the proposed approach solves $90\%$ of benchmark instances with $n \leq 3000$ to within $1\%$ optimality in at most three hours. This in turn demonstrates the remarkable strength of the proposed LP relaxations in both applications. Moreover, for more than $56\%$ of the instances, the proposed algorithm finds better solutions than those produced by popular fair Lloyd-type and spectral clustering heuristics.

Figures

Figures reproduced from arXiv: 2607.06709 by the authors.

Figure 1
Figure 1. Performance profile for 286 instances for fair K-means clustering. The curves show the [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗
Figure 2
Figure 2. Performance profile for 124 instances for spectral clustering. The curves show the per [PITH_FULL_IMAGE:figures/full_fig_p024_2.png] view at source ↗
Figure 3
Figure 3. Relative optimality gap δg over time for fair K-means clustering with α-fair constraints for the Student Math data set. Golden hexagons indicate the iterations in which the algorithm increases the separation parameter t. 30 [PITH_FULL_IMAGE:figures/full_fig_p030_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Relative optimality gap δg over time for fair K-means clustering with τ -fair constraints for the Student Math data set. Golden hexagons indicate the iterations in which the algorithm increases the separation parameter t. 31 [PITH_FULL_IMAGE:figures/full_fig_p031_4.png]
Figure 5
Figure 5. Figure 5: Relative optimality gap δg over time for fair K-means clustering with α-fair constraints and K = 5 clusters for three data sets. Golden hexagons indicate iterations in which the algorithm increases the separation parameter t. 32 [PITH_FULL_IMAGE:figures/full_fig_p032_5.png]
Figure 6
Figure 6. Figure 6: Relative optimality gap δg over time for fair K-means clustering with τ -fair constraints and K = 5 clusters for three data sets. Golden hexagons indicate iterations in which the algorithm increases the separation parameter t. 33 [PITH_FULL_IMAGE:figures/full_fig_p033…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    E. Abbe. Community Detection and Stochastic Block Models: Recent Developments.Journal of Machine Learning Research, 18:1 – 86, 2018

    work page 2018

  2. [2]

    Aloise, A

    D. Aloise, A. Deshpande, P. Hansen, and P. Popat. NP-hardness of Euclidean sum-of-squares clustering.Machine Learning, 75:245–248, 2009

    work page 2009

  3. [3]

    Awasthi, A

    P. Awasthi, A. S. Bandeira, M. Charikar, R. Krishnaswamy, S. Villar, and R. Ward. Relax, no need to round: Integrality of clustering formulations.Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 165:191–200, 2015

    work page 2015

  4. [4]

    S. Bera, D. Chakrabarty, N. Flores, and M. Negahbani. Fair algorithms for clustering.Advances in Neural Information Processing Systems, 32, 2019

    work page 2019

  5. [5]

    Chierichetti, R

    F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets.Advances in neural information processing systems, 30, 2017

    work page 2017

  6. [6]

    Conforti, G

    M. Conforti, G. Cornu´ ejols, and G. Zambelli.Integer Programming. In preparation, 2012

    work page 2012

  7. [7]

    De Rosa and A

    A. De Rosa and A. Khajavirad. The ratio-cut polytope and K-means clustering.SIAM Journal on Optimization, 32(1):173–203, 2022

    work page 2022

  8. [8]

    De Rosa, A

    A. De Rosa, A. Khajavirad, and Y. Wang. On the power of linear programming for k-means clustering.INFORMS Journal on Optimization, 2026

    work page 2026

Show all 30 references
  1. [9]

    Del Pia, A

    A. Del Pia, A. Khajavirad, and D. Kunisky. Linear programming and community detection.Mathematics of Operations Research, 48(2):885–913, 2023

    2023

  2. [10]

    D. Dua, C. Graff, et al. UCI machine learning repository.URL http://archive. ics. uci. edu/ml, 2017

    2017

  3. [11]

    Feldman, S

    M. Feldman, S. A. Friedler, J. Moeller, C. Scheidegger, and S. Venkatasubramanian. Certifying and removing disparate impact. Inproceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 259–268, 2015

    2015

  4. [12]

    Friggstad, M

    Z. Friggstad, M. Rezapour, and Salavatipour M. R. Local search yields a PTAS for K-means in doubling metrics. SIAM Journal on Computing, 48(2):452–480, 2019

    2019

  5. [13]

    Ghadiri, S

    M. Ghadiri, S. Samadi, and S. Vempala. Socially fair K-means clustering. InProceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 438–448, 2021

    2021

  6. [14]

    Gupta, G

    S. Gupta, G. Ghalme, N. C. Krishnan, and S. Jain. Efficient algorithms for fair clustering with a new notion of fairness.Data Mining and Knowledge Discovery, 37(5):1959–1997, 2023

    1959

  7. [15]

    Gurobi Optimizer Reference Manual, 2021

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL:https://www.gurobi.com

    2021

  8. [16]

    Iguchi, D

    T. Iguchi, D. G. Mixon, J. Peterson, and S. Villar. Probably certifiably correct K-means clustering.Mathematical Programming, 165:605–642, 2017

    2017

  9. [17]

    Kanungo, D.M

    T. Kanungo, D.M. Mount, N.S. Netanyahu, C.D. Piatko, R. Silverman, and A.Y. Wu. A local search approxi- mation algorithm for K-means clustering.Proceedings of the 18th Annual ACM Symposium on Computational Geometry, pages 10–18, 2002

    2002

  10. [18]

    Lawless and O

    C. Lawless and O. G¨ unl¨ uk. Fair minimum representation clustering. InInternational Conference on the In- tegration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 20–37. Springer, 2024

    2024

  11. [19]

    X. Li, Y. Li, S. Ling, T. Strohmer, and K. Wei. When do birds of a feather flock together? K-means, proximity, and conic programming.Mathematical Programming, 179:295–341, 2020. 28

    2020

  12. [20]

    Ling and T

    S. Ling and T. Strohmer. Certifying global optimality of graph cuts via semidefinite relaxation: A performance guarantee for spectral clustering.Foundations of Computational Mathematics, 20(3):367–421, 2020

    2020

  13. [21]

    S. Lloyd. Least squares quantization in PCM.IEEE Transactions on Information Theory, 28(2):129 –137, 1982

    1982

  14. [22]

    H. Lu, Z. Peng, and J. Yang. cuPDLPx: A further enhanced gpu-based first-order solver for linear programming. arXiv preprint arXiv:2507.14051, 2025

    2025

  15. [23]

    H. Lu, J. Yang, H. Hu, Q. Huangfu, J. Liu, T. Liu, Y. Ye, C. Zhang, and D. Ge. cuPDLP-C: A strengthened implementation of cupdlp for linear programming by c language.arXiv preprint arXiv:2312.14832, 2023

    2023 arXiv

  16. [24]

    Mahajan, P

    M. Mahajan, P. Nimbhorkar, and K. Varadarajan. The planar K-means problem is NP-hard. InWALCOM: Algorithms and Computation, pages 274–285. Springer Berlin Heidelberg, 2009

    2009

  17. [25]

    Marzi, F

    F. Marzi, F. Rossi, and S. Smriglio. Computational study of separation algorithms for clique inequalities.Soft Computing, 23(9):3013–3027, 2019

    2019

  18. [26]

    Neumaier and O

    A. Neumaier and O. Shcherbina. Safe bounds in linear and mixed-integer linear programming.Mathematical Programming, 99:283–296, 2004

    2004

  19. [27]

    Approximating K-means-type clustering via semidefinite programming.SIAM Journal on Optimization, 18(1):186–205, 2007

    J Peng and Y Wei. Approximating K-means-type clustering via semidefinite programming.SIAM Journal on Optimization, 18(1):186–205, 2007

    2007

  20. [28]

    Peng and Y

    J. Peng and Y. Xia.A New Theoretical Framework for K-Means-Type Clustering, pages 79–96. Springer Berlin Heidelberg, 2005

    2005

  21. [29]

    Von Luxburg

    U. Von Luxburg. A tutorial on spectral clustering.Statistics and Computing, 17(4):395–416, 2007

    2007

  22. [30]

    Wagner and F

    D. Wagner and F. Wagner. Between min cut and graph bisection. InInternational Symposium on Mathematical Foundations of Computer Science, pages 744–750. Springer, 1993. 29 Appendix In this appendix, we provide some details on the impact of parameterton the strength as well as t...

    1993

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.