## Approximating Discrete Collections via Local Improvements

Magnús M. Halldórsson

Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

We consider an old optimization technique and apply it to the
approximation of collections of discrete items. The technique is
local improvement search: attempt to extend a collection by adding
some items while removing others.
We obtain a (k+1)/2 performance ratio for k-DM, k-Set Packing,
and Independent Set problem in k+1-claw-free graphs by an NC
algorithm or in nearly-linear sequential time. It can be extended to
k/2 + epsilon (when k >= 4), and to (k+1)/3 + epsilon when
maximum degree is bounded.

We also obtain improved performance ratios for induced subgraph
problems, Independent Set in bounded-degree graphs, Vertex Cover in
claw-free graphs, Set Cover, and Graph Coloring under a complementary
objective function,