Exact Algorithms and Lower Bounds for Stable Instances of Euclidean \(\boldsymbol{k}\)- <scp>means</scp>
Bibliographic record
Abstract
Abstract. We investigate the complexity of solving stable or perturbation-resilient instances of [Formula: see text]-means and [Formula: see text]-median clustering in fixed-dimensional Euclidean metrics (or more generally doubling metrics). The notion of stable or perturbation-resilient instances was introduced by Bilu and Linial [ Are stable instances easy?, 2010] and Awasthi, Blum, and Sheffet [ Stability yields a PTAS for k-median and k-means clustering, IEEE Computer Society, Washington, DC, 2010]. In our context, we say a [Formula: see text]-means instance is [Formula: see text]-stable if there is a unique optimum solution which remains unchanged if distances are (nonuniformly) stretched by a factor of at most [Formula: see text]. Stable clustering instances have been studied to explain why heuristics such as Lloyd’s algorithm perform well in practice. In this work we show that for any fixed [Formula: see text], [Formula: see text]-stable instances of [Formula: see text]-means in doubling metrics, which include fixed-dimensional Euclidean metrics, can be solved in polynomial time. More precisely, we show a natural multiswap local-search algorithm in fact finds the optimum solution for [Formula: see text]-stable instances of [Formula: see text]-means and [Formula: see text]-median in a polynomial number of iterations. We complement this result by showing that it is essentially tight: when the dimension [Formula: see text] is part of the input there is a fixed [Formula: see text] such that there is not even a PTAS for [Formula: see text]-stable [Formula: see text]-means in [Formula: see text] with [Formula: see text] unless NP = RP. To do this, we consider a robust property of CSPs: call an instance stable if there is a unique optimum solution [Formula: see text] and for any other solution [Formula: see text], the number of unsatisfied clauses is proportional to the Hamming distance between [Formula: see text] and [Formula: see text]. Dinur, Goldreich, and Gur have already shown stable QSAT is hard to approximate for some constant [Formula: see text] [ 20 ]. Recently, Paradise [ Comput. Complexity, 30 (2021), 1] extended this to the setting with bounded variable occurrence. More specifically, this implies that stable QSAT with bounded variable occurrence is APX-hard. Given this, we consider “stability-preserving” reductions to prove our hardness for stable [Formula: see text]-means. Such reductions seem to be more fragile and intricate than standard [Formula: see text]-reductions and may be of further use to demonstrate other stable optimization problems are hard to solve.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.005 | 0.037 |
| Meta-epidemiology (narrow) | 0.004 | 0.002 |
| Meta-epidemiology (broad) | 0.003 | 0.004 |
| Bibliometrics | 0.003 | 0.007 |
| Science and technology studies | 0.004 | 0.004 |
| Scholarly communication | 0.011 | 0.017 |
| Open science | 0.012 | 0.008 |
| Research integrity | 0.005 | 0.009 |
| Insufficient payload (model declined to judge) | 0.038 | 0.007 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".