按年被提到
20122017 · 2 次2026
算法与数据结构›游戏复杂度与博弈论·arXiv:1205.0458 · cs.DS

Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection

靠偏置求平衡:最大平分问题的 0.8776 近似算法
Per Austrin, Siavosh Benabbas, Konstantinos Georgiou · 2012

把最大平分(Max Bisection)的近似比提高到 0.8776,接近 UGC 下的最优

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2017-01-04 · 最近 2021-10-28
3不同的人
3活跃月份
3讨论串
1被引(OpenAlex)

Raghavendra 与 Tan 曾给出最大平分问题的 0.85 近似算法,这篇论文把它改进到 0.8776。由于在唯一游戏猜想(UGC)下该问题难以近似到 α_GW+ε≈0.8786 之内,新算法接近最优。作者猜想最大平分可近似到 α_GW−ε,即平分约束基本不会让最大割更难,还为 Max 2-Sat 的类似变体得到(UGC 下)最优算法,近似比约 0.9401,改进了此前的 0.93。

HN 为什么提它

有人把它当作例子,说明理论上最好的近似算法虽然是多项式时间,但运行时间的指数大得离谱(约 O(n^(10^100))),实际毫无用处。

奠基之作难度 5 / 5约 90 分钟经得起时间
读之前最好知道
1近似算法与 NP 难
2半定规划(SDP)与 Goemans-Williamson 算法
3唯一游戏猜想(Unique Games Conjecture)
4最大割(Max Cut)问题

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用adrianN · 2017-01

“The best approximation algorithm (it's NP-hard) runs in time O(n^(10^100)):”

举它为例:最大平分的最佳近似算法运行时间大得离谱
引用mihaild · 2017-08

“For example, there is 0.8776-approximation that runs in about O(n^{10^100}) Better Balance by Being Biased”

举它为例:0.8776 近似虽是多项式时间,指数却极大
A Solution of the P versus NP Problem?原评论 ↗
引用skissane · 2021-10

“What about page 4 of [0]:”

指向它说明该算法虽是多项式时间却慢得离谱
The 50-year-old P-NP problem that eludes theoretical computer science原评论 ↗