Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems
Title | Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems |
Publication Type | Technical Report |
Year of Publication | 1997 |
Authors | Karpinski, M. |
Other Numbers | 1088 |
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. |
URL | http://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 |