Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems
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 noisy or partial predictions of an optimal solution let polynomial-time algorithms beat Goemans-Williamson's approximation barrier for MAXCUT and dense 2-CSPs, with theoretical guarantees only.
Problem
Approximation hardness of NP-hard offline maximization problems such as MAXCUT (GW ratio ~0.878 is UGC-optimal), where the goal is to use learned predictions of the optimal solution to beat worst-case approximation barriers.
Approach
Uses an epsilon-correlated prediction of the optimal cut (noisy, pairwise independent labels, or correct labels for a random epsilon-fraction of vertices) to guide an LP/SDP rounding: for dense (wide) vertices the predicted labels estimate neighborhood imbalances, enabling an LP whose rounding beats alpha_GW; narrow vertices are handled by an adapted Feige-Karpinski-Langberg/Hsieh-Kothari local-ga
Key results
- Noisy-prediction MAXCUT algorithm achieves alpha_GW + Omega~(eps^4) approximation in expectation, unconditionally beating the UGC-optimal GW ratio of ~0.878.
- Partial-prediction model yields alpha_RT + Omega(eps) (~0.858 base) approximation for MAXCUT, with the advantage linear in the prediction rate.
- Extends the noisy-prediction LP framework to dense 2-CSPs (Theorem 5.2), lowering the density threshold needed for near-1 approximation relative to Arora et al. 1999.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use pairwise-independent noisy predictions with bias ε | MAXCUT · MAXCUT | approximation factor: αGW + ˜Ω(ε4) | Helped |
| Use correct partial predictions for an ε-fraction of vertices | MAXCUT · MAXCUT | approximation factor: αGW + ε2 | Helped |
| Use marginal-preserving Raghavendra-Tan rounding with partial predictions | MAXCUT · MAXCUT | approximation factor: αRT + (1 − αRT − o(1))(2ε − ε2) | Helped |
| Use pairwise-independent noisy predictions with bias ε | MAX-2-CSP · Dense 2-CSP | value guarantee: optI − 5η − O (ε′) | Helped |
Surprising findings
- Partial predictions give an Omega(eps) advantage even though the rounding base ratio alpha_RT (~0.858) is below alpha_GW (~0.878).
Limitations
- Improvement for noisy predictions is only Omega~(eps^4), a small polynomial gain; exponent and constants not optimized.
- Analysis requires pairwise independence of predictions and the wide/narrow graph decomposition; low-degree (narrow) graphs are handled only with a weaker bound and no prediction use.
- No experiments; results are purely theoretical and no lower bounds beyond an SDP integrality-gap heuristic are proven.
Experimental setup
Metrics: approximation ratio
Baselines: Goemans-Williamson algorithm Raghavendra-Tan rounding Arora et al. 1999 dense CSP approximation
Builds on: Goemans-Williamson MAXCUT rounding Feige-Karpinski-Langberg algorithm Raghavendra-Tan max-bisection rounding Arora-Karger-Karpinski dense CSP approximation scheme
Closest papers by meaning
- Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems (ICML 2024 · similarity 0.89)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.89)
- Faster Global Minimum Cut with Predictions (ICML 2025 · similarity 0.88)
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.88)
- Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems (ICML 2025 · similarity 0.88)
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates (AAAI 2024 · similarity 0.87)
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.