文章基本信息

标题：On Some Tighter Inapproximability Results
本地全文：下载
作者：Piotr Berman ; Marek Karpinski
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：Approximation Algorithms, Approximation Hardness, Approximation Thresholds, Bounded MIS, Bounded MAX-2SAT, Bounded NodeCover, Computational Complexity, Sorting by Reversals