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 , 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.
Builds on7
- On Approximability of Satisfiable k-CSPs: IIAmey Bhangale, Subhash Khot, Dor MinzerSTOC 2023 · 7 citations
- On the Mysteries of MAX NAE-SATJoshua Brakensiek, Neng Huang, Aaron Potechin, Uri ZwickSODA 2021 · 6 citations
- Tight approximability of MAX 2-SAT and relatives, under UGCJoshua Brakensiek, Neng Huang, Uri ZwickSODA 2024 · 3 citations
- Separating MAX 2-AND, MAX DI-CUT and MAX CUTJoshua Brakensiek, Neng Huang, Aaron Potechin, Uri ZwickFOCS 2023 · 3 citations
- On Approximability of Satisfiable k-CSPs: IVAmey Bhangale, Subhash Khot, Dor MinzerSTOC 2024 · 2 citations
Related papers
- Approximation Algorithms and Hardness for Strong Unique GamesSuprovat Ghoshal, Anand LouisSODA 2021 · 3 citations
- A polynomial-time OPTɛ-approximation algorithm for maximum independent set of connected subgraphs in a planar graphJana Cslovjecsek, Michal Pilipczuk, Karol WegrzyckiSODA 2024 · 1 citation
- Half-Approximating Maximum Dicut in the Streaming SettingAmir Azarmehr, Soheil Behnezhad, Shane Ferrante, Mohammad SaneianSTOC 2026 · 3 citations
- Breaking the O(m2n)-Time Barrier for Vertex-Weighted Global Minimum CutJulia Chuzhoy, Ohad TrabelsiSTOC 2025 · 1 citation
- Online Dependent Rounding Schemes for Bipartite Matchings, withJoseph (Seffi) Naor, Aravind Srinivasan, David WajcSODA 2025 · 2 citations
