What is the best polynomial-time approximation ratio achievable for Max Di-Cut?
Max Di-Cut is the directed graph version of Max Cut: given a directed graph, find a partition of vertices maximizing the number of edges going from one side to the other.
Known bounds (assuming UGC): - Lower bound: 0.87446 (Brakensiek, Huang, Potechin, Zwick, 2023) - Upper bound: 0.87461 (Brakensiek, Huang, Potechin, Zwick, 2023)
This separates Max Di-Cut from Max Cut (which has optimal ratio ≈ 0.87856), resolving a question by Feige and Goemans. The lower bound uses experimentally-discovered rounding function distributions verified via computer-assisted proofs.
References: - Brakensiek, Huang, Potechin, Zwick. "Separating MAX 2-AND, MAX DI-CUT and MAX CUT" (FOCS 2023) - Code: https://github.com/jbrakensiek/max-dicut