Research map / Learning theory and algorithms / Clustering
Approximation Scheme for Weighted Metric Clustering via Sherali-Adams
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.
Shows that the Weighted Metric Clustering minimization problem admits a PTAS via a Sherali-Adams LP relaxation with independent rounding and outlier handling, and applies it to a new depth-based hierarchical clustering objective.
Problem
Minimizing a pairwise cost over k-partitions of metric points, where the cost matrix A weights inter-cluster distances; this generalizes Min-Uncut, Min-k-Sum, Min-k-Cut, multiway/multicut, manifold clustering, and hierarchical clustering. Prior minimization versions lacked PTAS guarantees and Sheral
Approach
Uses an r-round Sherali-Adams relaxation with local distributions made nearly independent (via conditioning) on candidate cluster sets, then independently rounds most points and handles low-probability outliers with a second LP objective (LPII) that bounds the error, giving a unified PTAS for all matrices A under the metric assumption.
Key results
- The Depth-HC objective achieves significantly higher dendrogram purity than Dasgupta's objective on 20 NEWSGROUPS subsamples, with the gap exceeding a factor of two at 10^4 points.
- The paper proves a PTAS (1+eps approximation with probability at least 1-eta) for Weighted Metric Clustering for any symmetric non-negative cost matrix A under the metric assumption.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the depth-based objective instead of Dasgupta’s objective | Hierarchical clustering on 20 NEWSGROUPS · 20 NEWSGROUPS subsamples (102, 103, and 104 points) | dendrogram purity: exceeding the factor of two for 104 points | Helped |
| use the depth-based objective instead of Dasgupta’s objective | Hierarchical clustering on 20 NEWSGROUPS · 20 NEWSGROUPS subsamples (102, 103, and 104 points) | complexity | Hurt |
Surprising findings
- Sherali-Adams relaxations can yield a PTAS for a minimization problem, despite prior belief that they only help for maximization CSPs (Yoshida-Zhou gave PTAS only for dense MAX-CSPs).
Limitations
- The PTAS runtime is exponential in the constant r and k and impractical in general; the experiments use a simplified 3-approximation LPII variant.
- Requires the metric assumption; without it no PTAS exists even for k=3 under UGC.
Experimental setup
Datasets: 20 NEWSGROUPS ZEBRAFISH CIFAR-10
Benchmarks: 20 NEWSGROUPS subsamples (100, 1000, 10000 points)
Metrics: dendrogram purity running time
Baselines: Dasgupta's objective with recursive Min-Cut
Builds on: Sherali-Adams hierarchy Raghavendra-Tan conditioning technique Yoshida-Zhou PTAS for dense MAX-CSP Dasgupta hierarchical clustering objective Makarychev-Makarychev-Razenshteyn outlier handling
Closest papers by meaning
- Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.86)
- Low-Distortion Clustering with Ordinal and Limited Cardinal Information (AAAI 2024 · similarity 0.86)
- Competitively Consistent 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)
- MC-GTA: Metric-Constrained Model-Based Clustering using Goodness-of-fit Tests with Autocorrelations (ICML 2024 · similarity 0.85)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.85)
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.