MAX BISECTION might be harder to approximate than MAX CUT
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 \(\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.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 5534–5557
- Publication date
- 1 January 2026
- Language
- EN