Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-029 | 27th May 1998 00:00

On Some Tighter Inapproximability Results

RSS-Feed

Abstract:

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 signed version
which is computable in polynomial time.



ISSN 1433-8092 | Imprint