Optimality Guarantees for Minimum Variance Subset Selection via Semidefinite Programming
Source: arxiv.org/abs/2611.13220
Given a set of data points in Euclidean space and a prescribed cardinality $k$, the minimum variance $k$-subset problem asks for $k$ points minimizing their average squared distance from their centroid. We develop a semidefinite programming (SDP) framework for exact recovery and global optimization. First, we show that the natural SDP relaxation fails Slater's condition. Identifying the proper face containing its feasible region yields an equivalent, lower-dimensional, strictly feasible formulation that enjoys strong duality. A primal--dual characterization of optimality then gives geometric…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.13220
curl -X POST /api/v1/records/arxiv/2611.13220/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.13220/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'