A scalable linear programming-based framework for data clustering

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\mathrm{\%}$ of benchmark instances with $n\le 3000$ to within $1\mathrm{\%}$ 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\mathrm{\%}$ of the instances, the proposed algorithm finds better solutions than those produced by popular fair Lloyd-type and spectral clustering heuristics.