P. Crescenzi, R. Silvestri, and L. Trevisan.
To Weight or not to Weight: Where is the Question?
In Proceedings of the 4th Israeli Symposium on Theory of Computing and Systems (ISTCS'96),
IEEE, pages 68-77, 1996.
Abstract
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 kSAT (for any k > 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.