Research map / Learning theory and algorithms / Clustering

A Batched Hartigan's $k$-Means Clustering

NeurIPS 2026 · Learning theory and algorithms › Clustering · approach: k-means++ seeding analysis

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.

Proposes a Batched Hartigan's k-means that vectorizes Hartigan's sequential updates by using the triangle inequality to identify parallel-safe point reassignments.

Problem

Hartigan's k-means has better theoretical properties than Lloyd's algorithm but is much slower in practice because its point-by-point updates are inherently sequential.

Approach

Exploits the triangle inequality to expose a large set of parallel-safe updates and a smaller set of sequential updates, enabling vectorized batched computation of Hartigan's algorithm.

Experimental setup

Baselines: Lloyd's k-means Hartigan's k-means

Builds on: Hartigan's k-means Lloyd's algorithm

Closest papers by meaning

• The Catastrophic Failure of *the* k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It (ICML 2026 · similarity 0.90)
• Multi-Swap k-Means++ (NeurIPS 2023 · similarity 0.86)
• Fast and Accurate $k$-means++ via Rejection Sampling (NeurIPS 2020 · similarity 0.86)
• A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++ (NeurIPS 2016 · similarity 0.86)
• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.85)
• Statistically Optimal $K$-means Clustering via Nonnegative Low-rank Semidefinite Programming (ICLR 2024 · similarity 0.83)