Research map / Learning theory and algorithms / Clustering
Consistent k-Clustering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Adding the option to recluster (allowing β-consistent changes) instead of irrevocable online decisions | online k-clustering · worst-case theory | consistency (number of changes): Ω(k log n) changes needed vs. online irrevocable (β=0) | Helped |
| Consistent k-clustering algorithm using Meyerson sketches with judicious reclustering | k-clustering under costp · worst-case theory | number of reclusterings: O(k^2 log^4 n) vs naive recluster every step | Helped |
| Running a single Meyerson sketch instead of O(log n) parallel sketches (ablation) | Consistent k-clustering implementation · SKINTYPE, SHUTTLE, COVERTYPE | approximation ratio | Hurt |
| Data order: non-random order of SKINTYPE vs randomly permuted | Consistent k-clustering reclustering rate · SKINTYPE | reclustering rate | No clear effect |
| Increasing k (10 to 100) | Consistent k-clustering reclustering rate · SKINTYPE, SHUTTLE, COVERTYPE | reclustering rate | Hurt |
Closest papers by meaning
- Competitively Consistent Clustering (ICML 2025 · similarity 0.90)
- Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering (NeurIPS 2024 · similarity 0.88)
- Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.87)
- Clustering with Non-adaptive Subset Queries (NeurIPS 2024 · similarity 0.87)
- Dynamic k-center clustering with lifetimes (NeurIPS 2026 · similarity 0.87)
- Learning-Augmented Algorithms for $k$-median via Online Learning (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.