Research map / Learning theory and algorithms / Clustering
Memory-Efficient Approximation Algorithms for Max-k-Cut and 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 |
|---|---|---|---|
| Run sampling-based SDP algorithm in linear memory on small-sparse graph | Max-Agree algorithm · GSET G1 | peak memory: 1526.35kB ≈ 9.8 x (|V|+|E+|+|E-|) x 8 | Helped |
| Check linear memory across all GSET instances | Max-Agree algorithm · GSET | memory constant c: c <= 33 | Helped |
| Check empirical approximation ratio against theoretical bound | Max-Agree algorithm · GSET, epsilon=0.05 | AR: 0.4375 -> 0.565 (lowest observed) | Helped |
| Compare best-of-10 rounding against theoretical bound on G14 | Max-Agree algorithm · GSET G14 | AR: 0.4375 -> 0.866 | Helped |
| Vary graph from G14 to G57 (more iterations, larger graph) | Max-Agree algorithm · GSET | AR: 0.866 -> 0.565 | Hurt |
| Pick the best of 10 Gaussian-sample clusterings | Max-Agree algorithm · GSET | clustering value | Helped |
| Check iteration count of LMO against theoretical bound | Frank-Wolfe solver · GSET | iterations to epsilon-convergence | No clear effect |
| Check infeasibility of covariance of generated samples | Algorithm 2 sampling · GSET | infeasibility: 0.004 max, below epsilon 0.05 | Helped |
Closest papers by meaning
- Instance-Specific Approximation Ratios for Correlation Clustering and Max-Cut (ICML 2026 · similarity 0.91)
- Fast Combinatorial Algorithms for Min Max Correlation Clustering (ICML 2023 · similarity 0.91)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.88)
- Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025 · similarity 0.88)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.87)
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better (ICML 2024 · similarity 0.86)
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.