{"ID":6138850,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-10T18:13:48.295420062Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.06709","arxiv_id":"2607.06709","title":"A scalable linear programming-based framework for data clustering","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.","short_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-matri...","url_abs":"https://arxiv.org/abs/2607.06709","url_pdf":"https://arxiv.org/pdf/2607.06709v1","authors":"[\"Aida Khajavirad\",\"Huanwen Shen\",\"Yakun Wang\"]","published":"2026-07-07T18:24:53Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}