Research map / Learning theory and algorithms / Clustering

A Beyond-Worst-Case Analysis of Greedy k-means++

NeurIPS 2025 · Learning theory and algorithms › Clustering · approach: k-means++ seeding analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Theoretical beyond-worst-case analysis of greedy k-means++ (sampling multiple candidates per step and greedily picking the best), explaining its empirically superior clustering cost relative to standard k-means++.

Problem

Greedy k-means++ is empirically better than k-means++ at seeding Lloyd's algorithm, but existing worst-case guarantees do not explain this advantage.

Approach

Analyzes greedy k-means++ beyond worst case, where in each iteration multiple (l >= 2) candidate seeds are sampled and the one greedily minimizing cost is chosen, to justify its superior practical performance.

Experimental setup

Baselines: k-means++

Builds on: k-means++

Closest papers by meaning

• A Better k-means++ Algorithm via Local Search (ICML 2019 · similarity 0.88)
• Fast and Accurate $k$-means++ via Rejection Sampling (NeurIPS 2020 · similarity 0.88)
• Greedy Sampling for Approximate Clustering in the Presence of Outliers (NeurIPS 2019 · similarity 0.88)
• k-variates++: more pluses in the k-means++ (ICML 2016 · similarity 0.88)
• Analyzing $D^\alpha$ seeding for $k$-means (ICML 2024 · similarity 0.85)
• Near-Linear Time Approximation Algorithms for k-means with Outliers (ICML 2024 · similarity 0.84)