As for problems like maximum sat, minimum vertex cover and maximum cut we do not known yet where they are.
| Finally we
have a problem in the upper rectangle, so we have one problem which is not
approximable. We have some problems which are approximable but are not in
the PTS class such as minimum bin packing and then we have problems in PTAS
which are not in the class PO. Moreover we have that the minimum graph coloring
problem certanly is not in PTS. As for problems like maximum sat, minimum vertex cover and maximum cut we do not known yet where they are. |
|
