Conference PaperA Local Search Algorithm for the Min-Sum Submodular Cover ProblemHellerstein, Lisa; Lidbetter, Thomas; Witter, R TealBae, Sang Won; Park, HeejinWe 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 Informatik2022-01-01104358102481868-8969978-3-95977-258-7https://doi.org/10.4230/LIPIcs.ISAAC.2022.31909335Local searchsubmodularitysecond-order supermodularitymin-sum set coverTheory of computation → Facility location and clustering13 pages749069 bytesapplication/pdfCreative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccessNational Science Foundation