Delphi.science

Optimality Guarantees for Minimum Variance Subset Selection via Semidefinite Programming

Source: arxiv.org/abs/2611.13220

Antonio M. Sudoso, Daniel Aloise

arXivarxiv/2611.13220Nov 9, 2026math.OCscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'