P. Crescenzi, R. Silvestri, and L. Trevisan.<br>
<b>To Weight or not to Weight: Where is the Question?</b><br>
In <i>Proceedings  of the 
<a href="http://www.cs.rice.edu/~vardi/istcs/">4th 
Israeli Symposium on Theory of 
Computing and Systems (ISTCS'96)</a></i>,<br>
IEEE, pages 68-77, 1996.

<dl>




<dt> <b> Abstract </b> <dd>


We study the approximability properties of several weighted problems, by 
comparing them with the respective unweighted problems. 
We show that
the weighted versions of Vertex Cover, Min SAT,
Max Cut, Max Directed Cut, Max 2SAT, and Max Exact <i>k</i>SAT
(for any <i>k</i>  > 1) are exactly as hard to approximate as their unweighted
versions. We note in passing that Vertex Cover
is exactly as hard to approximate
as Min SAT. The reductions for Max 2SAT, Max Cut, Max Directed Cut,
and Max Exact 3SAT give
new non-approximability results for these problems.

</dl>