Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
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_ | 1866909447883849728 |
|---|---|
| author | Dong, Yinhao Peng, Pan Vakilian, Ali |
| author_facet | Dong, Yinhao Peng, Pan Vakilian, Ali |
| contents | We study learning-augmented streaming algorithms for estimating the value of MAX-CUT in a graph. In the classical streaming model, while a $1/2$-approximation for estimating the value of MAX-CUT can be trivially achieved with $O(1)$ words of space, Kapralov and Krachun [STOC'19] showed that this is essentially the best possible: for any $ε> 0$, any (randomized) single-pass streaming algorithm that achieves an approximation ratio of at least $1/2 + ε$ requires $Ω(n / 2^{\text{poly}(1/ε)})$ space. We show that it is possible to surpass the $1/2$-approximation barrier using just $O(1)$ words of space by leveraging a (machine learned) oracle. Specifically, we consider streaming algorithms that are equipped with an $ε$-accurate oracle that for each vertex in the graph, returns its correct label in $\{-1, +1\}$, corresponding to an optimal MAX-CUT solution in the graph, with some probability $1/2 + ε$, and the incorrect label otherwise. Within this framework, we present a single-pass algorithm that approximates the value of MAX-CUT to within a factor of $1/2 + Ω(ε^2)$ with probability at least $2/3$ for insertion-only streams, using only $\text{poly}(1/ε)$ words of space. We also extend our algorithm to fully dynamic streams while maintaining a space complexity of $\text{poly}(1/ε,\log n)$ words. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_09773 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learning-Augmented Streaming Algorithms for Approximating MAX-CUT Dong, Yinhao Peng, Pan Vakilian, Ali Data Structures and Algorithms We study learning-augmented streaming algorithms for estimating the value of MAX-CUT in a graph. In the classical streaming model, while a $1/2$-approximation for estimating the value of MAX-CUT can be trivially achieved with $O(1)$ words of space, Kapralov and Krachun [STOC'19] showed that this is essentially the best possible: for any $ε> 0$, any (randomized) single-pass streaming algorithm that achieves an approximation ratio of at least $1/2 + ε$ requires $Ω(n / 2^{\text{poly}(1/ε)})$ space. We show that it is possible to surpass the $1/2$-approximation barrier using just $O(1)$ words of space by leveraging a (machine learned) oracle. Specifically, we consider streaming algorithms that are equipped with an $ε$-accurate oracle that for each vertex in the graph, returns its correct label in $\{-1, +1\}$, corresponding to an optimal MAX-CUT solution in the graph, with some probability $1/2 + ε$, and the incorrect label otherwise. Within this framework, we present a single-pass algorithm that approximates the value of MAX-CUT to within a factor of $1/2 + Ω(ε^2)$ with probability at least $2/3$ for insertion-only streams, using only $\text{poly}(1/ε)$ words of space. We also extend our algorithm to fully dynamic streams while maintaining a space complexity of $\text{poly}(1/ε,\log n)$ words. |
| title | Learning-Augmented Streaming Algorithms for Approximating MAX-CUT |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.09773 |