Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2000 Copyright 2000 Universität Bonn, Institut für Informatik, Abt. V
85213

Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems (Extended Version)
Marek Karpinski
[Download PostScript] [Download PDF]

We survey recent results on the existence of polynomial time approximation schemes for some dense instances of NP-hard combinatorial optimization problem. We indicate further some inherent limits for existence of such schemes for some other dense instances of optimization problems. We also go beyond the dense optimization problems and show how other approximation problems can be solved by using dense techniques.

Last Change: 11/05/14 at 10:18:44
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope