Research map / Learning theory and algorithms / Combinatorial and search optimization
Polynomial Time Learning Augmented Algorithms for NP-hard Permutation 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 pairwise order predictions (correct with probability 1/2+ε) let NP-hard permutation problems with decomposable or c-local objectives be solved exactly in polynomial time w.h.p. using O(n log n) queries.
Problem
NP-hard permutation optimization problems (e.g., scheduling, network design, graph permutation problems) where pairwise precedence predictions are noisy; the goal is exact polynomial-time solution with few predictions.
Approach
Adapts Braverman and Mossel's noisy sorting result: O(n log n) noisy pairwise queries yield an approximate position for each element within O(log n), which turns the problem into a k-position-enhanced instance (k=O(log n)) solvable by dynamic programming under a decomposition or c-locality property.
Key results
- Under the model where each pairwise prediction is correct with probability at least 1/2+ε, decomposable or c-local permutation problems are solvable exactly in polynomial time w.h.p. using O(n log n) prediction queries.
- Optimal NSWR permutation satisfies max_i |σ*(i)-π*(i)| = O(log n) w.h.p., enabling a k-position-enhanced DP with k=O(log n) running in time O(2^{O(k)} n^2) for decomposable problems.
- Under ETH, O(log n)-position-enhanced Permutation Clique and f(n)log n-position-enhanced Max Acyclic Subgraph and TSP are not solvable in polynomial time for any unbounded f, so the O(log n) bound is tight.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use pairwise predictions that are independently correct with probability at least 1/2+ε for a decomposable objective | Prediction-augmented framework · Decomposable permutation problems | exact solvability | Helped |
| Use pairwise predictions that are independently correct with probability at least 1/2+ε for a c-local objective | Prediction-augmented framework · c-local permutation problems | exact solvability | Helped |
| Limit prediction queries to O(n log n) | Prediction-augmented framework · Decomposable or c-local permutation problems | prediction queries: O(n \log n) | Helped |
| Provide only O(log n)-position enhancement | Permutation problems with decomposable or c-local objectives · O(log n)-position-enhanced problems | running time | Helped |
| Allow c log t position enhancement | Permutation Clique · Permutation Clique | polynomial-time solvability under ETH | Hurt |
| Allow f(n) log n position enhancement for unbounded increasing f | Max Acyclic Subgraph · Max Acyclic Subgraph | polynomial-time solvability under ETH | Hurt |
| Allow f(n) log n position enhancement for unbounded increasing f | TSP · TSP | polynomial-time solvability under ETH | Hurt |
Surprising findings
- Even with O(log n) position enhancement, Permutation Clique is not polynomial-time solvable under ETH, showing the enhancement alone is not always sufficient.
Limitations
- Exact polynomial-time solvability depends on decomposition or c-locality; not all permutation problems qualify.
- Some problems remain hard even with O(log n) position enhancement (e.g., Permutation Clique under ETH).
- Results are theoretical; no experiments are reported.
Experimental setup
Builds on: Braverman and Mossel noisy sorting (SODA 2008)
Closest papers by meaning
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.88)
- Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems (ICML 2024 · similarity 0.87)
- Improved Approximations for Hard Graph Problems using Predictions (ICML 2025 · similarity 0.86)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.86)
- Learning Augmented Exact Exponential Algorithms (NeurIPS 2026 · similarity 0.85)
- Differentiable extensions with rounding guarantees for combinatorial optimization over permutations (NeurIPS 2025 · similarity 0.85)
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.