On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms
<|reference_start|>On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms: 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.<|reference_end|>
@article{shi2024on,
    title={On Approximation of Robust Max-Cut and Related Problems using Randomized
  Rounding Algorithms},
    author={Haoyan Shi, Sanjay Mehrotra},
    journal={arXiv preprint arXiv:2406.01856},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.01856},
    primaryClass={cs.DS math.OC}
}