Separating MAX 2-AND, MAX DI-CUT and MAX CUT

Brakensiek, J; Huang, N; Potechin, A; Zwick, U

Brakensiek, J (通讯作者),Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA.

2023 IEEE 64TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, FOCS, 2023; (): 234

Abstract

Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is alpha(CUT)......

Full Text Link