Research map / Learning theory and algorithms / Clustering
Faster Approximation Algorithms for k-Center via Data Reduction
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.
Builds alpha-coresets for Euclidean k-Center (size k·o(n)) via a new polynomial-time consistent hashing and sampling-based covering, speeding up Gonzalez's algorithm 2–4x for large k.
Problem
Euclidean k-Center for large k is expensive (Gonzalez is O(nkd)); near-linear O(1)-approximation is open. The paper seeks data-reduction (coresets) that preserve approximation ratio and speed up existing algorithms.
Approach
Defines alpha-coresets (any beta-approximation on the coreset is an (alpha+beta)-approximation on P), constructs them as coverings via a randomly shifted grid viewed as a polynomial-time consistent hashing, plus a sampling-with-ANN covering construction; both are composed with JL projection.
Key results
- Coreset of size O(k n^{1/alpha^{2/3}}) computable in near-linear time gives O(alpha)-approximation for k-Center in time Õ(n + k^{1+1/alpha^2} n^{O(1/alpha^{2/3})}); for k=n^c, an O(1)-approximation in near-linear time.
- Consistent hashing with Λ = poly(d)·exp(O(d/β^{2/3})) and Γ = β evaluable in O(d) time, improving prior exp(d)-time constructions.
- Experiments: coreset-accelerated Gonzalez runs 2x-4x faster than full Gonzalez with cost within 1.3x on moderately large coreset sizes (k≈√n, four datasets).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Run Gonzalez on the proposed coreset instead of the full dataset | Gonzalez algorithm · Kddcup, Covertype, Census, Fashion-MNIST | speedup: 2x - 4x | Helped |
| Run Gonzalez on the proposed coreset instead of the full dataset | Gonzalez algorithm · Kddcup, Covertype, Census, Fashion-MNIST | clustering cost: within 1.3 times | Mixed |
| Use the proposed coreset instead of uniform sampling | Coreset construction · Kddcup, Covertype, Census, Fashion-MNIST | clustering cost | Helped |
| Add a random shift to the hash function (ablation) | Proposed coreset construction · Kddcup, Covertype, Census, Fashion-MNIST | clustering cost | Helped |
Limitations
- Coreset size depends exponentially on dimension unless JL reduction is applied
- Coreset guarantee is for approximation ratio only, not for cost on all center sets (weaker than strong coresets)
- Experiments limited to Gonzalez algorithm on four datasets with k≈√n
Experimental setup
Datasets: Kddcup Covertype Census Fashion-MNIST
Benchmarks: Kddcup Covertype Census Fashion-MNIST
Metrics: k-center clustering cost running time coreset size
Baselines: Gonzalez algorithm on full dataset (benchmark) uniform sampling coreset low-dimensional coreset (grid without random shift)
Builds on: Gonzalez farthest-point algorithm consistent hashing Johnson-Lindenstrauss lemma approximate nearest neighbor search for k-center
Closest papers by meaning
- Parameterized Approximation Algorithms for K-center Clustering and Variants (AAAI 2022 · similarity 0.92)
- Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse (ICML 2025 · similarity 0.88)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.86)
- Universal Weak Coreset (AAAI 2024 · similarity 0.86)
- Fully-Scalable Massively Parallel Algorithm for k-center with Outliers (AAAI 2025 · similarity 0.86)
- Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers (NeurIPS 2025 · similarity 0.86)
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.