# Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems

arXiv: https://arxiv.org/abs/2502.00841 · HTML: https://mlsanity.com/paper/2502.00841/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2025.

## Built on by (most cited first, 5 of 5)

- [Learning-Augmented Algorithms for Boolean Satisfiability](https://mlsanity.com/paper/2505.06146/) (2025)
- [Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling](https://mlsanity.com/paper/2606.13133/) (2026)
- [TSP with Predictions: Heatmap to Tour with Provable Guarantees](https://mlsanity.com/paper/2607.03791/) (2026)
- [CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees](https://mlsanity.com/paper/2607.14545/) (2026)
- [Robust Non-Clairvoyant Scheduling with Classification Models](https://mlsanity.com/paper/2610.01343/) (2026)

## Abstract (arXiv)

We consider a learning-augmented framework for NP-hard permutation problems. The algorithm has access to predictions telling, given a pair u,v of elements, whether u is before v or not in an optimal solution. Building on the work of Braverman and Mossel (SODA 2008), we show that for a class of optimization problems including scheduling, network design and other graph permutation problems, these predictions allow to solve them in polynomial time with high probability, provided that predictions are true with probability at least 1/2+ε. Moreover, this can be achieved with a parsimonious access to the predictions.