Improved Conic Reformulations for K-means Clustering

In this paper, we show that the popular $K$-means clustering problem can equivalently be reformulated as a conic program of polynomial size. The arising convex optimization problem is NP-hard, but ...

Computer Science Mathematics

View graph Source

Paper

References (25)

01Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic OptimizationNapat Rujeerapaiboon, K. Schindler, D. Kuhn et al.2017 · SIAM Journal on Optimization · 33 citations In Library

02Clustering subgaussian mixtures by semidefinite programmingD. Mixon, Soledad Villar, Rachel A. Ward2016 · arXiv.org · 104 citations In Library

03On the tightness of an SDP relaxation of k-meansTakayuki Iguchi, D. Mixon, Jesse Peterson et al.2015 · arXiv.org · 33 citations In Library

04Relax, No Need to Round: Integrality of Clustering FormulationsPranjal Awasthi, A. Bandeira, M. Charikar et al.2014 · Information Technology Convergence and Services · 122 citations In Library

05Nonnegative Sparse PCA with Provable GuaranteesMegasthenis Asteris, Dimitris Papailiopoulos, A. Dimakis2014 · International Conference on Machine Learning · 53 citations

06Representing quadratically constrained quadratic programs as generalized copositive programsS. Burer, Hongbo Dong2012 · Operations Research Letters · 75 citations

07Two algorithms for orthogonal nonnegative matrix factorization with application to clusteringF. Pompili, Nicolas Gillis, P. Absil et al.2012 · Neurocomputing · 169 citations In Library

08Data clustering: 50 years beyond K-meansAnil K. Jain2008 · Pattern Recognition Letters · 9.6k citations

09Convexity in SemiAlgebraic Geometry and Polynomial OptimizationJ. Lasserre2008 · SIAM Journal on Optimization · 131 citations

10NP-hardness of Euclidean sum-of-squares clusteringD. Aloise, A. Deshpande, P. Hansen et al.2008 · Machine-mediated learning · 1.0k citations

11Optimization Algorithms on Matrix ManifoldsP. Absil, R. Mahony, R. Sepulchre2007 · 1.1k citations

12Approximating K-means-type Clustering via Semidefinite ProgrammingJiming Peng, Yu Wei2007 · SIAM Journal on Optimization · 228 citations

Scroll for more · 13 remaining

Similar papers

Scalable Second-order Riemannian Optimization for $K$-means ClusteringPeng Xu, Chunyi Hou, Xiaohui Chen et al.2025 · arXiv.org · 0 citations In Library

A cutting plane algorithm for globally solving low dimensional k-means clustering problemsMartin Ryner, Jan Kronqvist, Johan Karlsson2024 · arXiv (Cornell University) · 0 citations In Library

When do birds of a feather flock together? k-Means, proximity, and conic programmingXiaodong Li, Yang Li, Shuyang Ling et al.2017 · Mathematical programming · 40 citations In Library

Mixed integer linear programming formulation for K-means clustering problemKolos Csaba Ágoston, Marianna E.-Nagy2023 · Central European Journal of Operations Research · 18 citations In Library

Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic OptimizationNapat Rujeerapaiboon, K. Schindler, D. Kuhn et al.2017 · SIAM Journal on Optimization · 33 citations In Library

An Effective and Efficient Algorithm for K-Means Clustering With New FormulationFeiping Nie, Ziheng Li, Rong Wang et al.2022 · IEEE Transactions on Knowledge and Data Engineering · 127 citations In Library

On the Power of Linear Programming for <i>K</i> -Means ClusteringAntonio De Rosa, Aida Khajavirad, Yakun Wang2026 · INFORMS Journal on Optimization In Library

Solving net-constrained clustering problem2024 · Journal of Nonlinear and Variational Analysis In Library

The Ratio-Cut Polytope and K-Means ClusteringAntonio De Rosa, Aida Khajavirad2020 · SIAM Journal on Optimization · 19 citations In Library

A Binary Optimization Approach for Constrained K-Means ClusteringHuu Le, Anders P. Eriksson, Thanh-Toan Do et al.2018 · Asian Conference on Computer Vision · 17 citations In Library

Patents near this paper

Approximate K-Means via Cluster ClosuresUS 9,710,493 · MICROSOFT CORPORATION · 2017 METHOD FOR REFINING THE INITIAL CONDITIONS FOR CLUSTERING WITH APPLICATIONS TO SMALL AND LARGE DATABASE CLUSTERINGUS 6,115,708 · MICROSOFT · 2000 METHOD AND APPARATUS FOR REDUCING THE COMPUTATIONAL REQUIREMENTS OF K-MEANS DATA CLUSTERINGUS 5,983,224 · HITACHI AMERICA, LTD. · 1999 FAST ALGORITHM FOR CONVEX OPTIMIZATION WITH APPLICATION TO DENSITY ESTIMATION AND CLUSTERINGUS 8,301,579 · XEROX CORPORATION · 2012 METHODS AND APPARATUS FOR EFFICIENT RESOURCE ALLOCATIONUS 4,885,686 · BELL TELEPHONE LABORTORIES, INCORPORATED · 1989

Source of record

arXiv