On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911902089609216 |
|---|---|
| author | Shi, Haoyan Mehrotra, Sanjay |
| author_facet | Shi, Haoyan Mehrotra, Sanjay |
| contents | Goemans and Williamson proposed a randomized rounding algorithm for the MAX-CUT problem with a 0.878 approximation bound in expectation. The 0.878 approximation bound remains the best-known approximation bound for this APX-hard problem. Their approach was subsequently applied to other related problems such as Max-DiCut, MAX-SAT, and Max-2SAT, etc. We show that the randomized rounding algorithm can also be used to achieve a 0.878 approximation bound for the robust and distributionally robust counterparts of the max-cut problem. We also show that the approximation bounds for the other problems are maintained for their robust and distributionally robust counterparts if the randomization projection framework is used. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_01856 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms Shi, Haoyan Mehrotra, Sanjay Data Structures and Algorithms Optimization and Control Goemans and Williamson proposed a randomized rounding algorithm for the MAX-CUT problem with a 0.878 approximation bound in expectation. The 0.878 approximation bound remains the best-known approximation bound for this APX-hard problem. Their approach was subsequently applied to other related problems such as Max-DiCut, MAX-SAT, and Max-2SAT, etc. We show that the randomized rounding algorithm can also be used to achieve a 0.878 approximation bound for the robust and distributionally robust counterparts of the max-cut problem. We also show that the approximation bounds for the other problems are maintained for their robust and distributionally robust counterparts if the randomization projection framework is used. |
| title | On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2406.01856 |