# Local Search for Clustering in Almost-linear Time

Preprint · Shaofeng H. -C. Jiang, Yaonan Jin, Jianing Lou, Pinyan Lu

- Archive id: arxiv:2504.03513
- Published: 2025-04-04
- arXiv: https://arxiv.org/abs/2504.03513
- Source URL: https://arxiv.org/abs/2504.03513
- PDF: https://arxiv.org/pdf/2504.03513
- Provenance: arxiv

## Abstract

We propose the first \\emph{local search} algorithm for Euclidean clustering that attains an $O(1)$-approximation in almost-linear time. Specifically, for Euclidean $k$-Means, our algorithm achieves an $O(c)$-approximation in $\\tilde{O}(n^{1 + 1 / c})$ time, for any constant $c \\ge 1$, maintaining the same running time as the previous (non-local-search-based) approach \[la Tour and Saulpic, arXiv'2407.11217\] while improving the approximation factor from $O(c^{6})$ to $O(c)$. The algorithm generalizes to any metric space with sparse spanners, delivering efficient constant approximation in $\\ell\_p$ metrics, doubling metrics, Jaccard metrics, etc. This generality derives from our main technical contribution: a local search algorithm on general graphs that obtains an $O(1)$-approximation in almost-linear time. We establish this through a new $1$-swap local search framework featuring a novel swap selection rule. At a high level, this rule \`\`scores'' every possible swap, based on both its modification to the clustering and its improvement to the clustering objective, and then selects those high-scoring swaps. To implement this, we design a new data structure for maintaining approximate nearest neighbors with amortized guarantees tailored to our framework.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.