MAX BISECTION might be harder to approximate than MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2026年份
摘要
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.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
它引用的顶会 Paper7
- On Approximability of Satisfiable k-CSPs: IIAmey Bhangale, Subhash Khot, Dor MinzerSTOC 2023 · 被引用 7 次
- On the Mysteries of MAX NAE-SATJoshua Brakensiek, Neng Huang, Aaron Potechin, Uri ZwickSODA 2021 · 被引用 6 次
- Tight approximability of MAX 2-SAT and relatives, under UGCJoshua Brakensiek, Neng Huang, Uri ZwickSODA 2024 · 被引用 3 次
- Separating MAX 2-AND, MAX DI-CUT and MAX CUTJoshua Brakensiek, Neng Huang, Aaron Potechin, Uri ZwickFOCS 2023 · 被引用 3 次
- On Approximability of Satisfiable k-CSPs: IVAmey Bhangale, Subhash Khot, Dor MinzerSTOC 2024 · 被引用 2 次
相关 Paper
- Approximation Algorithms and Hardness for Strong Unique GamesSuprovat Ghoshal, Anand LouisSODA 2021 · 被引用 3 次
- A polynomial-time OPTɛ-approximation algorithm for maximum independent set of connected subgraphs in a planar graphJana Cslovjecsek, Michal Pilipczuk, Karol WegrzyckiSODA 2024 · 被引用 1 次
- Half-Approximating Maximum Dicut in the Streaming SettingAmir Azarmehr, Soheil Behnezhad, Shane Ferrante, Mohammad SaneianSTOC 2026 · 被引用 3 次
- Breaking the O(m2n)-Time Barrier for Vertex-Weighted Global Minimum CutJulia Chuzhoy, Ohad TrabelsiSTOC 2025 · 被引用 1 次
- Online Dependent Rounding Schemes for Bipartite Matchings, withJoseph (Seffi) Naor, Aravind Srinivasan, David WajcSODA 2025 · 被引用 2 次
