MAX BISECTION might be harder to approximate than MAX CUT.

Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick

Browse the full SODA paper archive.