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

Joshua Brakensiek, Neng Huang, Aaron Potechin +1

Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is ${\alpha }_{\text{CUT}}\simeq 0.87856$, obtained…