Research map / Learning theory and algorithms / Combinatorial and search optimization
Approximation algorithms for combinatorial optimization with predictions
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.
Proposes a black-box method turning any approximation algorithm for linear selection problems into a learning-augmented one using possibly infeasible predictions, with approximation ratio degrading smoothly in prediction error, plus a refined Steiner Tree algorithm and UGC-based lower bounds.
Problem
Offline combinatorial selection problems (e.g., Vertex Cover, Steiner Tree, Min-Weight Perfect Matching, Knapsack, Clique) are NP-hard, and improving classic approximation guarantees usually costs much more running time; the question is how to use possibly infeasible predictions to improve approxima
Approach
Zero out the weights of predicted items and run an off-the-shelf approximation algorithm, which yields a feasible solution whose ratio is 1+(η+ + (ρ-1)η-)/OPT; for maximization, run the complementary problem with weights zeroed outside the prediction. A refined Steiner Tree algorithm scales predicted edge weights by a parameter α to avoid costly false positives.
Key results
- Black-box reduction gives approximation 1+(η+ + (ρ-1)η-)/OPT with the same running time as the base algorithm; e.g., linear-time 1+(η+ + η-)/OPT for Min-Weight Vertex Cover and Steiner Tree (via Mehlhorn).
- UGC-based lower bound: for Minimum Vertex Cover, no polynomial-time learning-augmented algorithm can achieve a ratio 1+f(x,y) with f(x,y) < x+y, so the black-box guarantee is optimal for the class.
- On PACE 2018 Steiner Tree instances, ALPS with alpha around 1.4-2 on accurate predictions yields solutions nearly as good as CIMAT while running at Mehlhorn's speed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ALPS with good predictions (low p) and α ≥ 1.4 instead of Mehlhorn | Steiner Tree · PACE 2018 instances | solution cost | Helped |
| Use ALPS with moderate α (α ≤ 2) when predictions are poor | Steiner Tree · PACE 2018 instances | solution cost relative to Mehlhorn | No clear effect |
| Use synthetic predictions with p=1.0 and small α instead of Mehlhorn | Steiner Tree · PACE 2018 instances | solution cost | Helped |
| Increase α when predictions are accurate; decrease α when predictions are bad (ablation) | ALPS · Steiner Tree | solution cost | Mixed |
| Choose a single α=1.4 or α=2 instead of searching over α values (ablation) | ALPS · Steiner Tree | solution cost | No clear effect |
Surprising findings
- Even nearly random synthetic predictions (p=1.0) improve over Mehlhorn's algorithm for small alpha on PACE instances, attributed to symmetry breaking on hard instances.
- The refined Steiner Tree algorithm stays robust (never significantly worse than Mehlhorn) for moderate alpha without an explicit robustification step.
Limitations
- Tight UGC lower bounds apply to the class as a whole; refined bounds require problem-specific analysis (shown only for Steiner Tree).
- Experiments are limited to Steiner Tree and the empirical standard deviations are sizable (up to 0.25 of values) due to limited iterations.
- Learning predictions is assumed PAC-learnable but computationally expensive learning is not implemented beyond majority vote.
Experimental setup
Datasets: PACE 2018 Steiner Tree heuristic track instances (199 graphs from SteinLib)
Benchmarks: PACE 2018 Steiner Tree heuristic track
Metrics: approximation ratio normalized cost relative to optimum and Mehlhorn
Baselines: Mehlhorn's algorithm CIMAT
Builds on: Mehlhorn 2-approximation for Steiner Tree folklore 2-approximation for Vertex Cover Chan's Knapsack approximation scheme
Closest papers by meaning
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.89)
- Improved Approximations for Hard Graph Problems using Predictions (ICML 2025 · similarity 0.88)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.87)
- Faster Global Minimum Cut with Predictions (ICML 2025 · similarity 0.86)
- Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems (ICML 2025 · similarity 0.86)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 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.