Lune

SODA2026Top-tier venue

MAX BISECTION might be harder to approximate than MAX CUT

Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick

2026Year

Abstract

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 [SODA'13, TALG'16] is whether MAX BISECTION can be approximated as well as MAX CUT, i.e., to within αGW≈0.8785672…\alpha_{\mathrm{GW}} \approx 0.8785672\ldots, which is the approximation ratio achieved by the celebrated Goemans-Williamson algorithm for MAX CUT, which is best possible assuming the Unique Games Conjecture (UGC). They conjectured that the answer is yes.

Ask about this paper

Your agent reads all of it.

Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.

Questions to start from

Your agent calls

Luneget_paper_fulltext

Ask in Lune

Free to start. No credit card required.

Builds on7

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines