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 Halldorsson 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 Hk - 1/2. In Color Saving, when larger independent sets exist, we can improve the performance ratio to 360/289.
|Number of pages
|Conference Proceedings of the Annual ACM Symposium on Theory of Computing
|Published - 1997
|Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997 → May 6 1997
All Science Journal Classification (ASJC) codes