Approximability of NP-hard problems

Research output: Contribution to journalConference articlepeer-review

41 Scopus citations


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 languageEnglish (US)
Pages (from-to)337-348
Number of pages12
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 1998
EventProceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA
Duration: May 23 1998May 26 1998

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Approximability of NP-hard problems'. Together they form a unique fingerprint.

Cite this