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 <I> denotes the encoding length of an instance I.