License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.3
URN: urn:nbn:de:0030-drops-172880
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17288/
Hellerstein, Lisa ;
Lidbetter, Thomas ;
Witter, R. Teal
A Local Search Algorithm for the Min-Sum Submodular Cover Problem
Abstract
We consider the problem of solving the Min-Sum Submodular Cover problem using local search. The Min-Sum Submodular Cover problem generalizes the NP-complete Min-Sum Set Cover problem, replacing the input set cover instance with a monotone submodular set function. A simple greedy algorithm achieves an approximation factor of 4, which is tight unless P=NP [Streeter and Golovin, NeurIPS, 2008]. We complement the greedy algorithm with analysis of a local search algorithm. Building on work of Munagala et al. [ICDT, 2005], we show that, using simple initialization, a straightforward local search algorithm achieves a (4+ε)-approximate solution in time O(n³log(n/ε)), provided that the monotone submodular set function is also second-order supermodular. Second-order supermodularity has been shown to hold for a number of submodular functions of practical interest, including functions associated with set cover, matching, and facility location. We present experiments on two special cases of Min-Sum Submodular Cover and find that the local search algorithm can outperform the greedy algorithm on small data sets.
BibTeX - Entry
@InProceedings{hellerstein_et_al:LIPIcs.ISAAC.2022.3,
author = {Hellerstein, Lisa and Lidbetter, Thomas and Witter, R. Teal},
title = {{A Local Search Algorithm for the Min-Sum Submodular Cover Problem}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {3:1--3:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17288},
URN = {urn:nbn:de:0030-drops-172880},
doi = {10.4230/LIPIcs.ISAAC.2022.3},
annote = {Keywords: Local search, submodularity, second-order supermodularity, min-sum set cover}
}
