MAX BISECTION might be harder to approximate than MAX CUT

Joshua Brakensiek, Neng Huang, Aaron Potechin +1

The MAX BISECTION problem seeks a maximum-size cut that evenly divides the vertices of a given undirected graph. An open problem raised by Austrin, Benabbas, and Georgiou is whethe…