A SURVEY OF APPROXIMATELY OPTIMAL-SOLUTIONS TO SOME COVERING AND PACKING PROBLEMS

We survey approximation algorithms for some well-known and very natura l combinatorial optimization problems, the minimum set covering, the m inimum vertex covering, the maximum set packing, and maximum independe nt set problems; we discuss their approximation performance and their complexity. For already known results, any time we have conceived simp ler proofs than those already published, we give these proofs, and, fo r the rest, we cite the simpler published ones. Finally, we discuss ho w one can relate the approximability behavior (from both a positive an d a negative point of view) of vertex covering to the approximability behavior of a restricted class of independent set problems.