2026-07-25T03:14:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17288 2024-03-06T10:59:22Z ddc:004 open_access

A Local Search Algorithm for the Min-Sum Submodular Cover Problem Hellerstein, Lisa Lidbetter, Thomas Witter, R. Teal Local search submodularity second-order supermodularity min-sum set cover 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lisa Hellerstein and Thomas Lidbetter and R. Teal Witter 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.3 urn:nbn:de:0030-drops-172880 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.3 eng https://creativecommons.org/licenses/by/4.0/legalcode