
handle: 11573/212660 , 2158/237695
We investigate the approximability properties of several weighted problems, by comparing them with the respective unweighted problems. For an appropriate (and very general) deenition 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. Then we turn our attention to specific problems, and we show that the un-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 Directed Cut, 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.
Approximation algorithms, approximation preserving reducibility, weighted optimization problem
Approximation algorithms, approximation preserving reducibility, weighted optimization problem
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
