Inapproximability of the Max-cut Problem with Negative Weights
Sung‐Pil Hong · Management Science and Financial Engineering · 2008
We show that when a max-cut problem is allowed native-weight edges, to decide if the problem has a cut of a positive weight is NP-hard. This implies that there is no polynomial time algorithm which guarantees a cut whose objective value is no less than 1/p(〈Ⅰ〉) times the optimum for any polynomially computable polynomial p, where 〈Ⅰ〉 denotes the encoding length of an instance Ⅰ.