{"id":"arxiv:2504.03513","kind":"preprint","title":"Local Search for Clustering in Almost-linear Time","authors":["Shaofeng H. -C. Jiang","Yaonan Jin","Jianing Lou","Pinyan Lu"],"author_count":4,"year":2025,"published":"2025-04-04","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2504.03513","nct_id":null,"source_url":"https://arxiv.org/abs/2504.03513","archive_url":"https://space-kitty.com/papers/arxiv:2504.03513","updated":"2025-04-04","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2504.03513","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}