Approximation of k -set cover by semi-local optimization
Rong-chii Duh, Martin Fürer · 1997
We define a powerful new approximation technique called semi-local optimization.It provides very natural heuristics that are distinctly more powerful than those based on local optimization.With an appropriate metric, semi-local optimization can still be viewed as a local optimization, but it has the advantage of making global changes to an approximate solution.Semi-local optimization generalizes recent heuristics of Halld6rsson for 3-Set Cover, Color Saving, and k-Set Cover.Greatly improved performance ratios of 4/3 for 3-Set Cover and 6/5 for Color Saving in graphs without independent sets of size 4 are obtained and shown to be the best possible with semi-local optimization.Also, based on the result for 3-Set Cover and a restricted greedy phase for big sets, we can improve the performance ratio for k-Set Cover to ~k -1/2.In Color Saving, when larger independent sets exist, we can improve the performance ratio to ~.