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

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. To appear in Proc. 1st Symp. on Randomization and Approximation Techniques in Computer Science (invited paper), July 11-12, 1997, Bologna. y Dept. of Computer Science, University of Bonn, 53117 Bonn, and the International Computer Science Institute, Berkeley, California. Email: marek@cs.bonn.edu. Research partially supported by the DFG Grant KA 673 4-1, and by the ESPRIT BR Grants 7097 and EC-US 030, by DIMACS, and by the Max-Planck Research Prize. 1 Introduction The computational efficiency of approximating different NP-hard optimization problems varies a great deal. We know by now, that unless P=NP, some problems, such as CLIQUE cannot be approximated in polynomial time even within a factor n 1\Gammaffl ..