Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914806186901504 |
|---|---|
| author | Bampis, Evripidis Escoffier, Bruno Xefteris, Michalis |
| author_facet | Bampis, Evripidis Escoffier, Bruno Xefteris, Michalis |
| contents | The classical work of (Arora et al., 1999) provides a scheme that gives, for any $ε>0$, a polynomial time $1-ε$ approximation algorithm for dense instances of a family of $\mathcal{NP}$-hard problems, such as Max-CUT and Max-$k$-SAT. In this paper we extend and speed up this scheme using a logarithmic number of one-bit predictions. We propose a learning augmented framework which aims at finding fast algorithms which guarantees approximation consistency, smoothness and robustness with respect to the prediction error. We provide such algorithms, which moreover use predictions parsimoniously, for dense instances of various optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02062 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems Bampis, Evripidis Escoffier, Bruno Xefteris, Michalis Data Structures and Algorithms The classical work of (Arora et al., 1999) provides a scheme that gives, for any $ε>0$, a polynomial time $1-ε$ approximation algorithm for dense instances of a family of $\mathcal{NP}$-hard problems, such as Max-CUT and Max-$k$-SAT. In this paper we extend and speed up this scheme using a logarithmic number of one-bit predictions. We propose a learning augmented framework which aims at finding fast algorithms which guarantees approximation consistency, smoothness and robustness with respect to the prediction error. We provide such algorithms, which moreover use predictions parsimoniously, for dense instances of various optimization problems. |
| title | Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.02062 |