Polynomial time approximation of dense weighted instances of MAX‐CUT

We give the first polynomial time approximability characterization of denseweighted instances of MAX‐CUT, and some other dense weighted 𝒩𝒫‐hard problems in terms of their empirical weight distributions. This also gives the first almost sharp characterization of inapproximability of unweighted 0, 1 MAX‐BISECTION instances in terms of their density parameter. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 314–332, 2000