TY - GEN

T1 - A Local Search-Based Approach for Set Covering

AU - Gupta, Anupam

AU - Lee, Euiwoong

AU - Li, Jason

N1 - Publisher Copyright:
Copyright © 2023 by SIAM.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85171559637&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85171559637&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85171559637

T3 - Proceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023

SP - 1

EP - 11

BT - Proceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023

A2 - Kavitha, Telikepalli

A2 - Mehlhorn, Kurt

PB - Society for Industrial and Applied Mathematics Publications

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

Y2 - 23 January 2023 through 25 January 2023

ER -