Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 1998 Copyright 1998 Universität Bonn, Institut für Informatik, Abt. V
8949

On Some Tighter Inaproximability Results
Piotr Berman, Marek Karpinski
[Download PostScript] [Download PDF]

We prove a number of improved inaproximability results, including the best up to date explicit approximation thresholds for MIS problem of bounded degree, bounded occurrences MAX-2SAT, and bounded degree Node Cover. We prove also for the first time inapproximability of the problem of Sorting by Reversals and display an explicit approximation threshold. This last problem was proved only recently to be NP-hard, in contrast to its \emph{signed} version which is computable in polynomial time.

Last Change: 11/05/14 at 10:11:02
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope