Approximation of k-Set Cover by semi-local optimization

Rong chii Duh, Martin Furer

Research output: Contribution to journalConference articlepeer-review

128 Scopus citations

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 languageEnglish (US)
Pages (from-to)256-264
Number of pages9
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1997
EventProceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997May 6 1997

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Approximation of k-Set Cover by semi-local optimization'. Together they form a unique fingerprint.

Cite this