Approximability of NP-hard problems

Sanjeev Arora

doi:10.1145/276698.276784

Approximability of NP-hard problems

Sanjeev Arora

Research output: Contribution to journal › Conference article › peer-review

44 Scopus citations

Abstract

For many NP-hard problems, achieving certain reasonable approximation ratios is no easier than computing optimal solutions. In other words, approximation is NP-hard. The negative results have fed an increased interest in approximation algorithms. The negative results of NP-hard problems such as MAX-CLIQUE, CHROMATIC NUMBER, MAX-3SAT, SET-COVER, and MAX-SNP are described. Some approximation algorithms that were recently discovered are presented.

Original language	English (US)
Pages (from-to)	337-348
Number of pages	12
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/276698.276784
State	Published - 1998
Event	Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA Duration: May 23 1998 → May 26 1998

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/276698.276784

Cite this

@article{24f9d9fafef24e96943c5ebb5463ab99,

title = "Approximability of NP-hard problems",

abstract = "For many NP-hard problems, achieving certain reasonable approximation ratios is no easier than computing optimal solutions. In other words, approximation is NP-hard. The negative results have fed an increased interest in approximation algorithms. The negative results of NP-hard problems such as MAX-CLIQUE, CHROMATIC NUMBER, MAX-3SAT, SET-COVER, and MAX-SNP are described. Some approximation algorithms that were recently discovered are presented.",

author = "Sanjeev Arora",

year = "1998",

doi = "10.1145/276698.276784",

language = "English (US)",

pages = "337--348",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing ; Conference date: 23-05-1998 Through 26-05-1998",

}

TY - JOUR

T1 - Approximability of NP-hard problems

AU - Arora, Sanjeev

PY - 1998

Y1 - 1998

N2 - For many NP-hard problems, achieving certain reasonable approximation ratios is no easier than computing optimal solutions. In other words, approximation is NP-hard. The negative results have fed an increased interest in approximation algorithms. The negative results of NP-hard problems such as MAX-CLIQUE, CHROMATIC NUMBER, MAX-3SAT, SET-COVER, and MAX-SNP are described. Some approximation algorithms that were recently discovered are presented.

AB - For many NP-hard problems, achieving certain reasonable approximation ratios is no easier than computing optimal solutions. In other words, approximation is NP-hard. The negative results have fed an increased interest in approximation algorithms. The negative results of NP-hard problems such as MAX-CLIQUE, CHROMATIC NUMBER, MAX-3SAT, SET-COVER, and MAX-SNP are described. Some approximation algorithms that were recently discovered are presented.

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

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

U2 - 10.1145/276698.276784

DO - 10.1145/276698.276784

M3 - Conference article

AN - SCOPUS:0031625439

SN - 0734-9025

SP - 337

EP - 348

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing

Y2 - 23 May 1998 through 26 May 1998

ER -

Approximability of NP-hard problems

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this