Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems

Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis, Panagiotis Patsilinakos, Michalis Xefteris
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:2790-2800, 2025.

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 this Paper

BibTeX
@InProceedings{pmlr-v267-bampis25a, 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}, pages = {2790--2800}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/bampis25a/bampis25a.pdf}, url = {https://proceedings.mlr.press/v267/bampis25a.html}, 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.} }
Endnote
%0 Conference Paper %T Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems %A Evripidis Bampis %A Bruno Escoffier %A Dimitris Fotakis %A Panagiotis Patsilinakos %A Michalis Xefteris %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-bampis25a %I PMLR %P 2790--2800 %U https://proceedings.mlr.press/v267/bampis25a.html %V 267 %X 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.
APA
Bampis, E., Escoffier, B., Fotakis, D., Patsilinakos, P. & Xefteris, M.. (2025). Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:2790-2800 Available from https://proceedings.mlr.press/v267/bampis25a.html.

Related Material