引用adrianN · 2017-01
“The best approximation algorithm (it's NP-hard) runs in time O(n^(10^100)):”
举它为例:最大平分的最佳近似算法运行时间大得离谱
把最大平分(Max Bisection)的近似比提高到 0.8776,接近 UGC 下的最优
Raghavendra 与 Tan 曾给出最大平分问题的 0.85 近似算法,这篇论文把它改进到 0.8776。由于在唯一游戏猜想(UGC)下该问题难以近似到 α_GW+ε≈0.8786 之内,新算法接近最优。作者猜想最大平分可近似到 α_GW−ε,即平分约束基本不会让最大割更难,还为 Max 2-Sat 的类似变体得到(UGC 下)最优算法,近似比约 0.9401,改进了此前的 0.93。
有人把它当作例子,说明理论上最好的近似算法虽然是多项式时间,但运行时间的指数大得离谱(约 O(n^(10^100))),实际毫无用处。
“The best approximation algorithm (it's NP-hard) runs in time O(n^(10^100)):”
“For example, there is 0.8776-approximation that runs in about O(n^{10^100}) Better Balance by Being Biased”
“What about page 4 of [0]:”