max cut

(Updated: )

max cut 近似比不能大于 16/17

[1] 中证明了, [2] 中也提到了这个结论

参考:

  1. Gadgets, Approximation, and Linear Programming
  2. Some Optimal Inapproximability Results