@inproceedings{
cohen-addad2024learningaugmented,
title={Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems},
author={Vincent Cohen-Addad and Tommaso d'Orsi and Anupam Gupta and Euiwoong Lee and Debmalya Panigrahi},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=mirkQqx6po}
}
In recent years, there has been a surge of interest in the use of machine-learned predictions to bypass worst-case lower bounds for classical problems in combinatorial optimization. So far, the focus has mostly been on online algorithms, where information-theoretic barriers are overcome using predictions about the unknown future. In this paper, we consider the complementary question of using learned information to overcome computational barriers in the form of approximation hardness of polynomial-time algorithms for NP-hard (offline) problems. We show that noisy predictions about the optimal solution can be used to break classical hardness results for maximization problems such as the max-cut problem and more generally, maximization versions of constraint satisfaction problems (CSPs).
Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems
Vincent Cohen-Addad Tommaso d'Orsi Anupam Gupta Euiwoong Lee Debmalya Panigrahi