Research map / Learning theory and algorithms / Clustering
Randomized Dimensionality Reduction for Facility Location and Single-Linkage 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 |
|---|---|---|---|
| project onto low dimension (d=20) before computing the MST | MST on Faces and MNIST '2' · Faces; MNIST '2' | running time: 80x speedup (Faces), 30x (MNIST '2') | Helped |
| project onto low dimension before MST (cost distortion) | MST on Faces and MNIST '2' · Faces; MNIST '2' | ratio of projected-tree cost to true MST cost | No clear effect |
| project to lower dimension for facility location | Facility location (Mettu-Plaxton) on Faces and MNIST '2' · Faces; MNIST '2' | solution cost ratio and runtime: runtime 1-2 orders of magnitude lower | Helped |
| low doubling dimension dataset vs high doubling dimension dataset for MST projection (ablation) | MST projection dimension needed · Synthetic n=1000 (Dataset 1 vs Dataset 2) | projection dimension for 10% relative MST error: d=10 vs d=38 | Helped |
Closest papers by meaning
- Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees (ICML 2025 · similarity 0.88)
- Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures (ICML 2025 · similarity 0.87)
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.85)
- New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering (ICML 2024 · similarity 0.85)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.85)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · 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.