Separating MAX 2-AND, MAX DI-CUT, and MAX CUT
SIAM Journal on Computing · 30.06.2026 · 55 (3) · FOCS23-268-FOCS23-308
DOI: 10.1137/24m1635776 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 28.05.2026. Verfasst von Joshua Brakensiek und 3 weiteren Autor:innen. Die Arbeit nennt 47 Literaturangaben. Gefördert von: National Science Foundation, Microsoft Research, ISF.
Abstract (Originalsprache)
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 .
Förderung
- National Science Foundation
- Microsoft Research
- ISF
Zitieren
APA
Brakensiek, J., Huang, N., Potechin, A., & Zwick, U. (2026). Separating MAX 2-AND, MAX DI-CUT, and MAX CUT. SIAM Journal on Computing, 55(3), FOCS23-268-FOCS23-308. https://doi.org/10.1137/24m1635776
Vancouver
Brakensiek J, Huang N, Potechin A, Zwick U. Separating MAX 2-AND, MAX DI-CUT, and MAX CUT. SIAM Journal on Computing. 2026;55(3):FOCS23-268-FOCS23-308. doi:10.1137/24m1635776
BibTeX
@article{Brakensiek2026,
author = {Brakensiek, Joshua and Huang, Neng and Potechin, Aaron and Zwick, Uri},
title = {Separating MAX 2-AND, MAX DI-CUT, and MAX CUT},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {3},
pages = {FOCS23--268--FOCS23--308},
doi = {10.1137/24m1635776}
}
EUVIMED