Talk:Karp's 21 NP-complete problems

From Wikipedia, the free encyclopedia

[edit] Approximability

I thought that MAX-CUT could be easily approximated to within a factor of 2 (and also within a factor of 1/0.8... using semi-definite programming). How can a special case not be approximable within any constant factor? LachlanA (talk) 19:06, 21 February 2008 (UTC)

Look at the cited paper. The standard optimization problem is approximable, but it has another optimization version that is not. Dcoetzee 19:13, 21 February 2008 (UTC)