So we have seen examples of problems like minimum bin packing, maximum sat, maximum cut and minimum vertex cover.
| In this lecture
we have seen examples of problems in class NPO. These problems admit a polynomial-time
r-approximation algorithm, for a given constant r. In this
case we call the problem r-approximable. So we have seen examples of problems like minimum bin packing, maximum sat, maximum cut and minimum vertex cover. |
|
