Since we have now different kind of problems, it seems reasonable to introduce the notion of approximation class. The first is the APS class, which contains all the optimization problems that admit a polynomial-time r-approximation algorithm, for a given constant r. The second is PTAS class, which contains all the optimization problems P that admit a polynomial-time r-approximation algorithm, for any r > 1. The difference between APS and PTAS is the fact that in the first case the constant r is fixed, while in PTAS the constant r is chosen by the user.

---