| In this talk, we shall discuss two new developments in the theory of approximation algorithms: NPO-completeness and PTAS. First, an NPO problem is an optimization problem and an NPO-complete problem is an NP-hard problem. It is similar to an NP-complete problem. Informally, an NPO-complete problem is a problem which is very unlikely to have any approximation algorithm which will yield constant ratio error rate. If any NPO-complete problem has a constant ratio error rate approximation algorithm, then all NPO problems have such kind of approximation algorithms. A PTAS (polynomial time approximation scheme) problem is just the opposite. Given any specified error rate, for a PTAS problem, there is always an approximation algorithm associated with this problem which produces a solution with constant ratio error rate and polynomial time complexity. Examples of both types of problems will be given. |