Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering
Abstract
Exact Euclidean K-means partitions n observations into K unlabelled clusters, but the unrestricted search is generally exponential. We use data-derived geometric graphs to precondition an exact subset dynamic program: as a result only connected vertex subsets are admitted as clusters, while sum-of-squared-errors (SSE) loss is unchanged. A remaining-set recurrence minimises fixed-K or penalised SSE, with exact factorisation over the connected components of each remaining set. The central question we study is how much computational support can be removed while preserving an unrestricted optimum. Graph inclusion gives monotone coverage and support relations, and a bottleneck threshold identifies the first covering graph in a nested hierarchy. For fixed K and dimension, under compact ball support and density bounds, retaining q=O(log n) nearest neighbours per observation preserves an empirical SSE optimum with probability tending to one, using an O(log n/n) fraction of complete-graph edges. Truncated Gaussian mixtures with unequal weights and covariances satisfy these conditions. The rate we provide is a sufficient upper bound rather than a result implying polynomial optimisation complexity. Objective-matched synthetic and full-data comparisons assess coverage, compression, and reference-label agreement. As a secondary application, we illustrate how the proposed scaffold preconditioning can be utilized to improve the efficiency of split-merge proposals that preserve unrestricted mixture posteriors.
Related
- Multi-period Value-at-Risk Constrained Portfolio Optimization via DC Programming
- Adaptive Variance-Reduced Stochastic Sequential (Quadratic Constrained) Quadratic Programming
- A New Perspective on Clustering: A Mixed-norm Model and its Solution by Progressive Integer Programming
- Timed Recovery Safe Gradient Flows for Constrained Nonlinear Programming
- On the Ω(n) SDP relaxation gap for Submodular Box-Constrained Quadratic Programming
BibTeX
@misc{raykov2026scaffoldconstrained,
title = {{Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering}},
author = {Yordan P. Raykov and Max A. Little},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30477},
eprint = {2609.30477},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30477},
}
RIS
TY - UNPB
TI - Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering
AU - Yordan P. Raykov
AU - Max A. Little
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.30477
UR - https://arxiv.org/abs/2609.30477
AB - Exact Euclidean K-means partitions n observations into K unlabelled clusters, but the unrestricted search is generally exponential. We use data-derived geometric graphs to precondition an exact subset dynamic program: as a result only connected vertex subsets are admitted as clusters, while sum-of-squared-errors (SSE) loss is unchanged. A remaining-set recurrence minimises fixed-K or penalised SSE, with exact factorisation over the connected components of each remaining set. The central question we study is how much computational support can be removed while preserving an unrestricted optimum. Graph inclusion gives monotone coverage and support relations, and a bottleneck threshold identifies the first covering graph in a nested hierarchy. For fixed K and dimension, under compact ball support and density bounds, retaining q=O(log n) nearest neighbours per observation preserves an empirical SSE optimum with probability tending to one, using an O(log n/n) fraction of complete-graph edges. Truncated Gaussian mixtures with unequal weights and covariances satisfy these conditions. The rate we provide is a sufficient upper bound rather than a result implying polynomial optimisation complexity. Objective-matched synthetic and full-data comparisons assess coverage, compression, and reference-label agreement. As a secondary application, we illustrate how the proposed scaffold preconditioning can be utilized to improve the efficiency of split-merge proposals that preserve unrestricted mixture posteriors.
ER -