TY - GEN
T1 - A Local Search Algorithm for the Min-Sum Submodular Cover Problem
AU - Hellerstein, Lisa
AU - Lidbetter, Thomas
AU - Witter, R. Teal
N1 - Publisher Copyright:
© Lisa Hellerstein, Thomas Lidbetter, and R. Teal Witter.
PY - 2022/12/1
Y1 - 2022/12/1
N2 - 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(n3 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.
AB - 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(n3 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.
KW - Local search
KW - min-sum set cover
KW - second-order supermodularity
KW - submodularity
UR - http://www.scopus.com/inward/record.url?scp=85144166017&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85144166017&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2022.3
DO - 10.4230/LIPIcs.ISAAC.2022.3
M3 - Conference contribution
AN - SCOPUS:85144166017
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 33rd International Symposium on Algorithms and Computation, ISAAC 2022
A2 - Bae, Sang Won
A2 - Park, Heejin
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 33rd International Symposium on Algorithms and Computation, ISAAC 2022
Y2 - 19 December 2022 through 21 December 2022
ER -