According to this classification the summary is represented in this picture. As you can see we have four classes:

  • the first class PO is the class of problems solvable in polynomial time;
  • the last class NPO is the class for all optimization problems;
  • and then in the middle we have the class that we have just defined: that is APX and PTAS.
At the end of the first part course we will show that minimum bin packing, maximum sat, maximum cut and minimum vertex cover problems belong to APX, and that minimum partition problem belongs to PTAS