ON THE COMPLEXITY OF APPROXIMATING THE INDEPENDENT SET PROBLEM

被引：67

作者：

BERMAN, P

SCHNITGER, G

机构：

[1] Department of Computer Science, The Pennsylvania State University, University Park

来源：

INFORMATION AND COMPUTATION | 1992年 / 96卷 / 01期

关键词：

18;

D O I：

10.1016/0890-5401(92)90056-L

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that for some positive constant c it is not feasible to approximate Independent Set (for graphs of n vertices) within a factor of nc, provided Maximum 2-Satisfiability does not have a randomized polynomial time approximation scheme. We also study reductions preserving the quality of approximations and exhibit complete problems. © 1992.

引用

页码：77 / 94

页数：18

共 17 条

[1]

[Anonymous], 1968, INTRO PROBABILITY TH

[2] TOWARD A UNIFIED APPROACH FOR THE CLASSIFICATION OF NP-COMPLETE OPTIMIZATION PROBLEMS [J].