Local Search for Clustering in Almost-linear Time

Description

We propose the first local search algorithm for Euclidean clustering that attains an 𝑂(1)-approximation in almost-linear time. Specifically, for Euclidean 𝑘-Means, our algorithm achieves an 𝑂(𝑐)-approximation in 𝑂 ̃(𝑛^(1+1/𝑐)) time, for any constant 𝑐≥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 𝑂(𝑐^6 ) to 𝑂(𝑐). The algorithm generalizes to any metric space with sparse spanners, delivering efficient constant approximation in ℓ_𝑝 metrics, doubling metrics, Jaccard metrics, etc.
 
This generality derives from our main technical contribution: a local search algorithm on general graphs that obtains an 𝑂(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.