We investigate the approximability properties of several weighted problems,
by comparing them with the respective unweighted problems. For an appropri
ate (and very general) definition of niceness. we show that if a nice weigh
ted problem is hard to approximate within r. then its polynomially bounded
weighted version is hard to approximate within r - o(1). Then we turn our a
ttention to specific problems. and we show that the unweighted versions of
MIN VERTEX COVER, MIN SAT. MAX CUT. MAX DICUT, MAX 2SAT, and MAX EXACT kSAT
are exactly as hard to approximate as their weighted versions. We note in
passing that MIN VERTEX COVER is exactly as hard to approximate as MIN SAT.
In order to prove the reductions for MAX 2SAT, MAX CUT, MAX DICUT, and MAX
E3SAT We introduce the new notion of "mixing" set and we give an explicit
construction of such sets. These reductions give new non-approximability re
sults for these problems. (C) 2001 Academic Press.