On the complexity of approximating the independent set problem

Piotr Berman; Georg Schnitger

doi:10.1016/0890-5401(92)90056-L

On the complexity of approximating the independent set problem

Piotr Berman, Georg Schnitger

Research output: Contribution to journal › Article › peer-review

91 Scopus citations

Abstract

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 n^c, 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.

Original language	English (US)
Pages (from-to)	77-94
Number of pages	18
Journal	Information and Computation
Volume	96
Issue number	1
DOIs	https://doi.org/10.1016/0890-5401(92)90056-L
State	Published - Jan 1992

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Computer Science Applications
Computational Theory and Mathematics

Access to Document

10.1016/0890-5401(92)90056-L

Cite this

@article{302502b6e0624cccbda5763d9e968ace,

title = "On the complexity of approximating the independent set problem",

abstract = "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.",

author = "Piotr Berman and Georg Schnitger",

year = "1992",

month = jan,

doi = "10.1016/0890-5401(92)90056-L",

language = "English (US)",

volume = "96",

pages = "77--94",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - On the complexity of approximating the independent set problem

AU - Berman, Piotr

AU - Schnitger, Georg

PY - 1992/1

Y1 - 1992/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0026624588&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026624588&partnerID=8YFLogxK

U2 - 10.1016/0890-5401(92)90056-L

DO - 10.1016/0890-5401(92)90056-L

M3 - Article

AN - SCOPUS:0026624588

SN - 0890-5401

VL - 96

SP - 77

EP - 94

JO - Information and Computation

JF - Information and Computation

IS - 1

ER -

On the complexity of approximating the independent set problem

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this