Research map / Learning theory and algorithms / Clustering
How to Find a Good Explanation for 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 |
|---|---|---|---|
| Use a greedy sequence of cuts, removing points so each cut separates whole clusters | Clustering Explanation · Given k-clustering in R^d | approximation ratio: (k-1)-approximation | Helped |
| Use dynamic programming over bounding boxes and cluster-splitting choices | Clustering Explanation · Given k-clustering in R^d | running time: 2^{2\min\{s,k\}}\cdot n^{2d}\cdot (dn)^{\mathcal{O}(1)} | Helped |
| Mark the first and last s+1 points per cluster and coordinate, then preserve coordinate order in the reduced instance | Clustering Explanation · Given k-clustering in R^d | number of points in equivalent instance: r = 2 (s + 1) dk | Helped |
| Branch over canonical threshold cuts at each internal tree node | Explainable k-means and k-median · Unrestricted dimension | running time: (nd)^{k+\mathcal{O}(1)} | Helped |
| Use dynamic programming over canonical bounding boxes | Explainable k-means and k-median · Unrestricted dimension | running time: n^{2d}\cdot (dn)^{\mathcal{O}(1)} | Helped |
| Allow a small fraction of outliers while targeting the optimal explainable-clustering cost | Approximate Explainable Clustering · n points in R^d | running time: (\frac{8dk}{\epsilon})^k\cdot n^{\mathcal{O}(1)} | Helped |
| Restrict the problem to constant k or constant d | Explainable k-means and k-median · Unrestricted input size | running time: (4nd)^{k+\mathcal{O}(1)}; n^{2d}\cdot n^{\mathcal{O}(1)} | Helped |
| Attempt exact optimization of explainable clustering with parameter k | Explainable k-means and k-median · Unless ETH fails | running time lower bound: f(k)\cdot n^{o(k)} | Hurt |
Closest papers by meaning
- Explainable k-Means and k-Medians Clustering (ICML 2020 · similarity 0.92)
- Dynamic Algorithm for Explainable $k$-medians Clustering under $\ell_p$ Norm (NeurIPS 2025 · similarity 0.91)
- Explaining Kernel Clustering via Decision Trees (ICLR 2024 · similarity 0.90)
- SpEx: A Spectral Approach to Explainable Clustering (NeurIPS 2025 · similarity 0.90)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.84)
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.84)
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.