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,