Key points are not available for this paper at this time.
Goemans와 Williamson은 MAX-CUT 문제를 위한 무작위 반올림 알고리즘을 제안하였으며, 기대값에 대해 0.878의 근사 경계를 갖습니다. 0.878 근사 경계는 이 APX-하드 문제에 대해 알려진 가장 좋은 근사 경계로 남아 있습니다. 그들의 접근법은 이후 Max-DiCut, MAX-SAT, Max-2SAT 등과 같은 다른 관련 문제에도 적용되었습니다. 우리는 무작위 반올림 알고리즘이 맥스 컷 문제의 강인한 및 분포적으로 강인한 대응 문제에 대해 0.878의 근사 경계를 달성하는 데 사용될 수 있음을 보여줍니다. 또한 무작위화 투영 프레임워크가 사용될 경우 다른 문제들의 근사 경계는 그들의 강인한 및 분포적으로 강인한 대응 문제에서도 유지된다는 것을 보여줍니다.
Shi 외 (Mon,) 연구한 바 있습니다.