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)|
|Number of pages||12|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - Jan 1 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