Research map / Learning theory and algorithms / Clustering

Online Clustering with Nearly Optimal Consistency

ICLR 2025 · 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.

Gives online algorithms for k-Means and (k,z)-Clustering that achieve nearly optimal consistency by converting any offline approximation algorithm into an online one.

Problem

Online clustering (k-Means and (k,z)-Clustering) where the algorithm must maintain centers over arriving points while limiting how often its solution changes, measured by consistency.

Approach

A reduction that turns any alpha-approximate offline clustering algorithm into an online algorithm with (1+epsilon)alpha^2 competitive ratio and O(k polylog n) consistency, nearly matching the lower bound on consistency.

Key results

• Turns any alpha-approximate offline clustering algorithm into an (1+epsilon)alpha^2-competitive online algorithm.
• Achieves O(k polylog n) consistency, stated to be optimal up to polylog factors.

Experimental setup

Metrics: competitive ratio consistency

Builds on: Lattanzi & Vassilvitskii 2017 consistency notion

Closest papers by meaning

• Consistent k-Clustering (ICML 2017 · similarity 0.92)
• Near-Optimal $k$-Clustering in the Sliding Window Model (NeurIPS 2023 · similarity 0.89)
• Online Differentially Private Consistent Clustering (NeurIPS 2026 · similarity 0.89)
• Competitively Consistent Clustering (ICML 2025 · similarity 0.89)
• Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.87)
• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.87)