Metraipolis › archive › dc_4e38f6090aa6

Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering — arXiv:2609.30477

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.30477
License (as archived)
CC0-1.0
Archived
2026-10-08T02:19:07.667Z
SHA-256 of the archived text
115b35ae552ed2cb5a3923eb01d08707381edeab5e100c2e970bdfddcadc48dd
Stable URL of this page
https://metraipolis.com/documento/dc_4e38f6090aa6

How to cite

Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering — arXiv:2609.30477 — arXiv (en), https://arxiv.org/abs/2609.30477 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4e38f6090aa6 (Metraipolis archive dc_4e38f6090aa6, sha256 115b35ae552ed2cb5a3923eb01d08707381edeab5e100c2e970bdfddcadc48dd)
BibTeX
@misc{dc4e38f6090aa6,
  title = {Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering — arXiv:2609.30477},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.30477},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4e38f6090aa6; sha256 115b35ae552ed2cb5a3923eb01d08707381edeab5e100c2e970bdfddcadc48dd},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.30477. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-28 in cs.LG).
Categorie arXiv: Statistics Theory (math.ST) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.30477 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T01:43:06.778Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).