Research map / Learning theory and algorithms / Clustering
Fast Combinatorial Algorithms for Min Max Correlation 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 correlation metric (combinatorial rounding) instead of solving LP (KMZ) | Min Max correlation clustering · Five small Facebook ego-networks | objective (Min Max disagreements): ours 72/34/47/20/12 vs KMZ 89/38/69/18/13 | No clear effect |
| Use correlation metric rounding instead of Pivot | Min Max correlation clustering · Five small Facebook ego-networks | objective (Min Max disagreements): e.g. FB 348: 72 vs Pivot 85.03; FB 686: 47 vs 65.72 | Helped |
| Use correlation metric rounding instead of Pivot | Min Max correlation clustering · Five larger Facebook ego-networks | objective (Min Max disagreements): FB 0: 49 vs 71.78; FB 107: 152 vs 216.65; FB 1912: 220 vs 259.01 | Helped |
| Use correlation metric rounding instead of Pivot on FB 3437 | Min Max correlation clustering · FB 3437 | objective (Min Max disagreements): 107 vs Pivot 99.1 (worse) | Mixed |
| Exact correlation metric (no sampling) vs LP-based KMZ runtime | Min Max correlation clustering · FB 348 (224 vertices) | run-time: tenth of a second vs KMZ over 30 minutes | Helped |
| Set rounding radii r1=r2=0.7 instead of theoretical 1/5 and 2/5 (ablation) | Our algorithm · Facebook ego-networks | objective (Min Max disagreements): practical radii used; theory uses r1=1/5, r2=2/5 | Helped |
| Sampling-based estimates of correlation metric (O(n^2 log n / eps^2)) instead of exact computation | Our algorithm · Theoretical analysis | approximation factor / run-time: constant c(eps) approximation vs 40 for exact | Mixed |
| Scale to ~10,000 vertices with exact correlation metric | Our algorithm · ca-HepPh (12008 vertices) | run-time (s): 250.91 s | Helped |
Closest papers by meaning
- Instance-Specific Approximation Ratios for Correlation Clustering and Max-Cut (ICML 2026 · similarity 0.92)
- Towards Better-than-2 Approximation for Constrained Correlation Clustering (ICML 2025 · similarity 0.90)
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better (ICML 2024 · similarity 0.89)
- Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering (NeurIPS 2025 · similarity 0.89)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.89)
- Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025 · similarity 0.89)
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.