  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.
