We prove that the subdense instances of MAX-CUT of average
degree Omega(n/logn) posses a polynomial time approximation scheme (PTAS).
We extend this result also to show that the instances of general 2-ary
maximum constraint satisfaction problems (MAX-CSP) of the same average
density have PTASs. Our results ... more >>>