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

Abstract. Assuming the unique games conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the max cut problem is [Formula: see text], obtained by the celebrated SDP-based approximation algorithm of Goemans and Williamson. The current best approximation algorithm for max di-cut, i.e., the max cut problem in directed graphs, achieves a ratio of about 0.87401, leaving open the question of whether max di-cut can be approximated as well as max cut. We obtain a slightly improved algorithm for max di-cut and a new UGC-hardness for it, showing that [Formula: see text], where [Formula: see text] is the best approximation ratio that can be obtained in polynomial time for max di-cut under UGC. Our new upper bound shows that max di-cut cannot be approximated as well as max cut, which separates max di-cut from max cut and resolves a question raised by Feige and Goemans. A natural generalization of max di-cut is the max [Formula: see text]-and problem in which each constraint is of the form [Formula: see text], where [Formula: see text] and [Formula: see text] are literals, i.e., variables or their negations (in max di-cut each constraint is of the form [Formula: see text] where [Formula: see text] and [Formula: see text] are variables). Austrin separated max [Formula: see text]-and from max cut by showing that [Formula: see text] and conjectured that max [Formula: see text]-and and max di-cut have the same approximation ratio. Our new lower bound on max di-cut refutes this conjecture, completing the separation of the three problems max [Formula: see text]-and, max di-cut, and max cut. We also obtain a new lower bound for max [Formula: see text]-and, showing that [Formula: see text]. Our upper bound on max di-cut is achieved via a simple, analytical proof. The new lower bounds on max di-cut and max [Formula: see text]-and, i.e., the new approximation algorithms, use experimentally discovered distributions of rounding functions which are then verified via computer-assisted proofs. Code for the project is available at https://github.com/jbrakensiek/max-dicut .