Approximation of k-set cover by semi-local optimization
- 1 January 1997
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 256-264
- https://doi.org/10.1145/258533.258599
Abstract
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 ...Keywords
This publication has 0 references indexed in Scilit: