Research map / Learning theory and algorithms / Clustering
Clustering What Matters: Optimal Approximation for Clustering with Outliers
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 |
|---|---|---|---|
| Reduce k-MedianOut to k-Median using a ring-sampled coreset and enumerate candidate outliers | k-MedianOut · General metrics | approximation ratio: $6.387$ to $(1+\frac{2}{e}+\epsilon)$ | Helped |
| Apply the reduction framework to k-MeansOut | k-MeansOut · General metrics | approximation ratio: $53.002$ to $(1+\frac{8}{e} + \epsilon)$ | Helped |
| Use the outlier-free approximation as a black box through the reduction | k-MedianOut · Constant-doubling-dimension and listed sparse graph metrics | approximation ratio: $(1+\epsilon)$ | Helped |
| Use the reduction with matroid constraints | Matroid Median with Outliers · General metrics | approximation ratio: $(2+\epsilon)$ | Helped |
| Construct a coreset separately for each color class, then use color-agnostic enumeration | Colorful k-Median · General metrics | approximation ratio: $(1+\frac{2}{e} + \epsilon)$ | Helped |
| Use the general reduction for k-MedianOut | k-MedianOut · General metrics | approximation ratio: $3+\epsilon$ to $(1+\frac{2}{e}+\epsilon)$ | Helped |
| Use the general reduction for k-MeansOut | k-MeansOut · General metrics | approximation ratio: $9+\epsilon$ to $(1+\frac{8}{e} + \epsilon)$ | Helped |
Closest papers by meaning
- A More Efficient Reduction from Outlier-Aware to Outlier-Free k-Median (AAAI 2026 · similarity 0.92)
- A Practical Algorithm for Distributed Clustering and Outlier Detection (NeurIPS 2018 · similarity 0.91)
- Fast Algorithms for Distributed k-Clustering with Outliers (ICML 2023 · similarity 0.91)
- Near-Linear Time Approximation Algorithms for k-means with Outliers (ICML 2024 · similarity 0.90)
- Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.88)
- Parameterized Approximation Schemes for Fair-Range Clustering (NeurIPS 2024 · 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.