We survey 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.