id: 01853175
dt: j
an: 01853175
au: Crescenzi, Pierluigi; Silvestri, Riccardo; Trevisan, Luca
ti: On weighted vs unweighted versions of combinatorial optimization problems.
so: Inf. Comput. 167, No.1, 10-26 (2001).
py: 2001
pu: Elsevier Science (Academic Press), San Diego, CA
la: EN
cc: G.1.6 F.1.3
ut: 
ci: 
li: doi:10.1006/inco.2000.3011
ab: Summary: We investigate the approximability properties of several weighted
    problems, by comparing them with the respective unweighted problems.
    For an appropriate (and very general) definition of niceness, we show
    that if a nice weighted 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 attention 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 $k$SAT 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 results for these problems.
rv: