We give the first polynomial time approximability characterization of dense weighted instances of MAX-CUT, and some other dense weighted ${\cal NP}$-hard problems in terms of their empirical weight distributions.