Max-Cut with $ε$-Accurate Predictions
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916141575700480 |
|---|---|
| author | Cohen-Addad, Vincent d'Orsi, Tommaso Gupta, Anupam Lee, Euiwoong Panigrahi, Debmalya |
| author_facet | Cohen-Addad, Vincent d'Orsi, Tommaso Gupta, Anupam Lee, Euiwoong Panigrahi, Debmalya |
| contents | We study the approximability of the MaxCut problem in the presence of predictions. Specifically, we consider two models: in the noisy predictions model, for each vertex we are given its correct label in $\{-1,+1\}$ with some unknown probability $1/2 + ε$, and the other (incorrect) label otherwise. In the more-informative partial predictions model, for each vertex we are given its correct label with probability $ε$ and no label otherwise. We assume only pairwise independence between vertices in both models.
We show how these predictions can be used to improve on the worst-case approximation ratios for this problem. Specifically, we give an algorithm that achieves an $α+ \widetildeΩ(ε^4)$-approximation for the noisy predictions model, where $α\approx 0.878$ is the MaxCut threshold. While this result also holds for the partial predictions model, we can also give a $β+ Ω(ε)$-approximation, where $β\approx 0.858$ is the approximation ratio for MaxBisection given by Raghavendra and Tan. This answers a question posed by Ola Svensson in his plenary session talk at SODA'23. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_18263 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Max-Cut with $ε$-Accurate Predictions Cohen-Addad, Vincent d'Orsi, Tommaso Gupta, Anupam Lee, Euiwoong Panigrahi, Debmalya Data Structures and Algorithms Computational Complexity F.0 We study the approximability of the MaxCut problem in the presence of predictions. Specifically, we consider two models: in the noisy predictions model, for each vertex we are given its correct label in $\{-1,+1\}$ with some unknown probability $1/2 + ε$, and the other (incorrect) label otherwise. In the more-informative partial predictions model, for each vertex we are given its correct label with probability $ε$ and no label otherwise. We assume only pairwise independence between vertices in both models. We show how these predictions can be used to improve on the worst-case approximation ratios for this problem. Specifically, we give an algorithm that achieves an $α+ \widetildeΩ(ε^4)$-approximation for the noisy predictions model, where $α\approx 0.878$ is the MaxCut threshold. While this result also holds for the partial predictions model, we can also give a $β+ Ω(ε)$-approximation, where $β\approx 0.858$ is the approximation ratio for MaxBisection given by Raghavendra and Tan. This answers a question posed by Ola Svensson in his plenary session talk at SODA'23. |
| title | Max-Cut with $ε$-Accurate Predictions |
| topic | Data Structures and Algorithms Computational Complexity F.0 |
| url | https://arxiv.org/abs/2402.18263 |