Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems

TitlePolynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems
Publication TypeTechnical Report
Year of Publication1997
AuthorsKarpinski, M.
Other Numbers1088
Abstract

We overview recent results on the existence of polynomial time approximation schemes for some dense instances of NP-hard optimization problems. We indicate further some inherent limits for existence of such schemes for some other dense instances of the optimization problems.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1997/tr-97-022.pdf
Bibliographic Notes

ICSI Technical Report TR-97-022

Abbreviated Authors

M. Karpinski

ICSI Publication Type

Technical Report