Lune

SODA2026顶会

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 α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.

问问这篇 Paper

智能体会读完全文。

Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。

可以从这些问题问起

智能体调用

Luneget_paper_fulltext

在 Lune 里问

免费开始,无需绑卡

它引用的顶会 Paper7

相关 Paper

黄昏的海面,两侧是细线勾勒的悬崖