99-23: On Some Tighter Inapproximability Results

DIMACS TR: 99-23

On Some Tighter Inapproximability Results

Authors: Piotr Berman and Marek Karpinski

ABSTRACT
We give a number of improved inapproximability results, including the best up to date explicit approximation thresholds for bounded occurrence satisfiability problems like MAX-2SAT and E2-LIN-2, and the bounded degree graph problems, like MIS, NodeCover, and MAX CUT. We prove also for the first time inapproximability of the problem of Sorting by Reversals and display an explicit approximation threshold.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-23.ps.gz

DIMACS Home Page