Research map / Learning theory and algorithms / Clustering

Competitively Consistent Clustering

ICML 2025 · Learning theory and algorithms › Clustering · approach: Coresets and dynamic clustering

Read the paperCheck your idea against 108,967 papers

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

Gives fully-dynamic k-center, facility location, and k-median algorithms with competitive recourse, via rounding fractional positive-body-chasing solutions, plus matching-up-to-log lower bounds.

Problem

Fully-dynamic consistent clustering (k-center, facility location, k-median) where data points arrive and depart; the goal is to keep an approximately optimal solution at all times while minimizing recourse (center additions/deletions) relative to the offline optimum with a beta-approximation.

Approach

Reduce fractional dynamic clustering to positive body chasing, then round the fractional solution online with a lazy ball-based greedy that drops centers only when their fractional mass dips, using a potential function over well-separated balls of different radii to bound recourse by O(log Delta) times fractional movement.

Key results

• Upper bounds: O(beta)-approximate solutions with recourse O(log|F| log Delta)*OPT^beta for facility location and k-median, and O((1/eps^2) log(|F|/eps) log Delta)*OPT^beta for k-center using (1+eps)k centers.
• Lower bound: any randomized algorithm with approximation alpha*beta has recourse Omega(min{log|F|, log_alpha Delta})*OPT^beta for these problems.
• Experiments on UCI datasets show objectives well below the worst-case bound alpha*beta*OPT and recourse often much smaller than T, sometimes below the offline fractional optimum recourse.

Measured effects reported in the paper

Surprising findings

• On several datasets the online algorithm's recourse is lower than the offline fractional optimum recourse, attributed to resource augmentation.
• Algorithms for k-center and k-median tend to use no more than k centers in practice despite being allowed (1+eps)k or O(k).

Limitations

• Upper and lower bounds differ by a log factor (log|F| vs min{log|F|, log Delta}).
• k-center and k-median use (1+eps)k or O(k) centers rather than exactly k; the k-median approximation has no extra 1/eps-factor-free version.

Experimental setup

Datasets: UCI Glass Identification UCI Wine Quality UCI Airfoil Self-Noise

Benchmarks: UCI Glass UCI Wine Quality UCI Airfoil Self-Noise

Metrics: objective value vs alpha*beta*OPT total recourse number of centers

Baselines: offline fractional optimum recourse

Builds on: positive body chasing (Bhattacharya, Buchbinder, Levin, Saranurak, FOCS 2023) greedy k-center 2-approximation Markov-inequality-based facility location rounding

Closest papers by meaning

• Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse (ICML 2025 · similarity 0.91)
• Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.90)
• Consistent k-Clustering (ICML 2017 · similarity 0.90)
• Dynamic k-center clustering with lifetimes (NeurIPS 2026 · similarity 0.89)
• Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.88)
• New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering (ICML 2024 · similarity 0.87)