The Ratio-Cut Polytope and K-Means Clustering

DOI10.1137/20M1348601zbMath1486.90120arXiv2006.15225OpenAlexW4214500875MaRDI QIDQ5062119

Aida Khajavirad, Antonio De Rosa

Publication date: 15 March 2022

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.15225

zbMATH Keywords

linear programming\(K\)-means clusteringstochastic ball modelratio-cut polytope

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Variational problems in a geometric measure-theoretic setting (49Q20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Local Versions of Sum-of-Norms Clustering, Efficient joint object matching via linear programming, SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering, Mixed-integer programming techniques for the minimum sum-of-squares clustering problem

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Unnamed Item
• Graph partitioning using linear and semidefinite programming
• On the minimum of the mean-squared error in 2-means clustering
• Probably certifiably correct \(k\)-means clustering
• Random Laplacian matrices and convex relaxations
• Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
• When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Exact Recovery in the Stochastic Block Model
• Relax, No Need to Round
• The Planar k-Means Problem is NP-Hard
• Improved Conic Reformulations for $K$-means Clustering
• A local search approximation algorithm for k-means clustering
• Clustering subgaussian mixtures by semidefinite programming
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• High-Dimensional Probability
• Least squares quantization in PCM
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Cluster Analysis and Mathematical Programming
• Geometry of cuts and metrics