A Local Search-Based Approach for Set Covering

Anupam Gupta, Euiwoong Lee, Jason Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In the Set Cover problem, we are given a set system with each set having a weight, and we want to find a collection of sets that cover the universe, whilst having low total weight. There are several approaches known (based on greedy approaches, relax-and-round, and dual-fitting) that achieve a Hk ≈ ln k+O(1) approximation for this problem, where the size of each set is bounded by k. Moreover, getting a ln k−O(ln ln k) approximation is hard. Where does the truth lie? Can we close the gap between the upper and lower bounds? An improvement would be particularly interesting for small values of k, which are often used in reductions between Set Cover and other combinatorial optimization problems. We consider a non-oblivious local-search approach: to the best of our knowledge this gives the first Hkapproximation for Set Cover using an approach based on local-search. Our proof fits in one page, and gives a integrality gap result as well. Refining our approach by considering larger moves and an optimized potential function gives an (Hk − Ω(log2 k)/k)-approximation, improving on the previous bound of (Hk − Ω(1/k8)) (R. Hassin and A. Levin, SICOMP’05) based on a modified greedy algorithm.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
EditorsTelikepalli Kavitha, Kurt Mehlhorn
PublisherSociety for Industrial and Applied Mathematics Publications
Number of pages11
ISBN (Electronic)9781611977585
StatePublished - 2023
Event2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023 - Florence, Italy
Duration: Jan 23 2023Jan 25 2023

Publication series

NameProceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023


Conference2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'A Local Search-Based Approach for Set Covering'. Together they form a unique fingerprint.

Cite this