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
8952

On Some Tighter Inapproximability Results, Further Improvements
Marek Karpinski, Piotr Berman
[Download PostScript] [Download PDF]

Improved inaproximability results are given, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems, like MAX-2SAT and E2-LIN-2, and problems in bounded degree graphs, like MIS, Node Cover and MAX CUT. We prove also for the first time inapproximability of the problem of Sorting by Reversals and display an explicit approximation threshold for this problem.

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