# Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization

arXiv: https://arxiv.org/abs/1705.07837 · HTML: https://mlsanity.com/paper/1705.07837/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2017.

## Built on by (most cited first, 6 of 6)

- [The Hidden Uniform Cluster Prior in Self-Supervised Learning](https://mlsanity.com/paper/2210.07277/) (2022)
- [Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming](https://mlsanity.com/paper/2209.08901/) (2022)
- [Cequel: Cost-Effective Querying of Large Language Models for Text Clustering](https://mlsanity.com/paper/2504.15640/) (2025)
- [No More Than 6ft Apart: Robust K-Means via Radius Upper Bounds](https://mlsanity.com/paper/2203.02502/) (2022)
- [Exact and Heuristic Algorithms for Constrained Biclustering](https://mlsanity.com/paper/2508.05493/) (2025)
- [Mind the Gaps: Auditing and Reducing Group Inequity in Large-Scale Mobility Prediction](https://mlsanity.com/paper/2510.26940/) (2025)

## Abstract (arXiv)

Plain vanilla K-means clustering has proven to be successful in practice, yet it suffers from outlier sensitivity and may produce highly unbalanced clusters. To mitigate both shortcomings, we formulate a joint outlier detection and clustering problem, which assigns a prescribed number of datapoints to an auxiliary outlier cluster and performs cardinality-constrained K-means clustering on the residual dataset, treating the cluster cardinalities as a given input. We cast this problem as a mixed-integer linear program (MILP) that admits tractable semidefinite and linear programming relaxations. We propose deterministic rounding schemes that transform the relaxed solutions to feasible solutions for the MILP. We also prove that these solutions are optimal in the MILP if a cluster separation condition holds.