Polynomial Time Learning Augmented Algorithms for NP-Hard Permutation Problems
Abstract
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+\epsilon$. Moreover, this can be achieved with a parsimonious access to the predictions.
Cite
Text
Bampis et al. "Polynomial Time Learning Augmented Algorithms for NP-Hard Permutation Problems." Proceedings of the 42nd International Conference on Machine Learning, 2025.Markdown
[Bampis et al. "Polynomial Time Learning Augmented Algorithms for NP-Hard Permutation Problems." Proceedings of the 42nd International Conference on Machine Learning, 2025.](https://mlanthology.org/icml/2025/bampis2025icml-polynomial/)BibTeX
@inproceedings{bampis2025icml-polynomial,
title = {{Polynomial Time Learning Augmented Algorithms for NP-Hard Permutation Problems}},
author = {Bampis, Evripidis and Escoffier, Bruno and Fotakis, Dimitris and Patsilinakos, Panagiotis and Xefteris, Michalis},
booktitle = {Proceedings of the 42nd International Conference on Machine Learning},
year = {2025},
pages = {2790-2800},
volume = {267},
url = {https://mlanthology.org/icml/2025/bampis2025icml-polynomial/}
}