Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems

Evripidis Bampis; Bruno Escoffier; Dimitris Fotakis; Panagiotis Patsilinakos; Michalis Xefteris

ICML 2025poster2 citations

Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems

Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis, Panagiotis Patsilinakos, Michalis Xefteris

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.

Learning-augmented algorithmsNP-hard permutation problemspredictions

BibTeX

@inproceedings{
bampis2025polynomial,
title={Polynomial Time Learning Augmented Algorithms for {NP}-hard Permutation Problems},
author={Evripidis Bampis and Bruno Escoffier and Dimitris Fotakis and Panagiotis Patsilinakos and Michalis Xefteris},
booktitle={Forty-second International Conference on Machine Learning},
year={2025},
url={https://openreview.net/forum?id=29bt3kWj2J}
}