Research map / Learning theory and algorithms / Combinatorial and search optimization
Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard 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.
Learning-augmented PTAS for dense NP-hard problems (Max-CUT, Max-k-SAT, Max-DICUT, Max-HYPERCUT, k-Densest Subgraph) using only O(log n) one-bit predictions on a sampled set of variables, giving polynomial running time independent of epsilon with consistency, smoothness and robustness.
Problem
Speeding up the Arora-Karger-Karpinski PTAS for dense instances of NP-hard problems such as Max-CUT and Max-k-SAT, whose running time is exponential in 1/epsilon, while using few predictions.
Approach
Sample O(log n) variables, obtain one-bit predictions for them at an optimal solution, estimate linear coefficients via sampling, then solve an LP relaxation with randomized rounding; for smooth polynomials this is done recursively via decomposition, and the approach is combined with a robust constant-factor algorithm (e.g., Goemans-Williamson) to form a learning-augmented approximation (LAA) sche
Key results
- For dense Max-CUT, LAA-Cut achieves (1-epsilon-8·error/(delta|S|))-approximation with high probability in time O(n·T_LP), with |S| = Theta(ln n/(epsilon^3 delta^4)) sampled vertices.
- Combined with Goemans-Williamson, the scheme's ratio is max{1-epsilon-8error/(delta|S|), 0.878}, versus the original PTAS running time of n^{1/(epsilon delta)^2}, which for epsilon=0.122 is about n^67.
- The general LA-PTAS for c-smooth degree-d PIPs runs in O(n ln(cn^d)·T'_LP) time with an additive loss of (epsilon + 4ced(d-1)error/|S|)n^d, with probability at least 1/2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sampled one-bit predictions in LA-PTAS-Cut | Dense Max-CUT · Dense Max-CUT | approximation ratio: 1 - \epsilon - 8\frac{\textit{error}}{\delta |S|} | Mixed |
| Use Goemans-Williamson alongside the prediction-based algorithm | LAA-Cut · Dense Max-CUT | approximation ratio: \max \{1 - \epsilon - 8\frac{\textit{error}}{\delta |S|}, 0.878 \} | Helped |
| Use logarithmically many predictions instead of exhaustive sample assignments | Dense Max-CUT · Dense Max-CUT | running time: O(2^{1/(ε δ)^2 log n}) = n^{1/ (ε δ)^2} -> O(n \cdot T_{LP}) | Helped |
| Use predictions with the general learning-augmented algorithm | LAA-General · Dense Max-DICUT | approximation ratio: 1 - \epsilon - 32e \frac{\textit{error}}{\delta |S|} | Mixed |
| Use predictions with the general learning-augmented algorithm | LAA-General · Dense Max-k-SAT | additive objective loss: \bigg(\epsilon+ 4ced(d-1)\frac{\textit{error}}{|S|}\bigg) n^{d} | Mixed |
Experimental setup
Metrics: approximation ratio running time
Baselines: Arora-Karger-Karpinski PTAS Goemans-Williamson de la Vega PTAS
Builds on: Arora-Karger-Karpinski PTAS Goemans-Williamson Lykouris-Vassilvitskii algorithms with predictions
Closest papers by meaning
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.89)
- Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems (ICML 2025 · similarity 0.87)
- Learning Augmented Exact Exponential Algorithms (NeurIPS 2026 · similarity 0.86)
- Improved Approximations for Hard Graph Problems using Predictions (ICML 2025 · similarity 0.85)
- Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs (NeurIPS 2026 · similarity 0.85)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · 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.