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 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.
Original language | English (US) |
---|---|
Pages (from-to) | 256-264 |
Number of pages | 9 |
Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |
DOIs | |
State | Published - 1997 |
Event | 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
- Software