A Local Search Algorithm for the Min-Sum Submodular Cover Problem
A Local Search Algorithm for the Min-Sum Submodular Cover Problem
复制标题
DOI：
10.48550/arxiv.2209.03054
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
L. Hellerstein;T. Lidbetter;R. T. Witter
中科院分区：
文献类型：
--
作者：
L. Hellerstein;T. Lidbetter;R. T. Witter
我们考虑使用局部搜索来解决最小和次模覆盖问题。Min-Sum Submodular Cover问题推广了NP-完全Min-Sum Set Cover问题，用单调子模集函数代替输入集覆盖实例。一个简单的贪婪算法实现了近似因子4，这是紧的，除非P=NP [Streeter和Golovin，NeurIPS，2008]。我们补充了贪婪算法的局部搜索算法的分析。在Munagala等人的工作的基础上。[ICDT，2005]，我们证明了，使用简单的初始化，一个简单的局部搜索算法在时间$O（n^3\log（n/\n））$内实现了$（4+\n）$-近似解，前提是单调子模集函数也是二阶超模。二阶超模块性已经被证明适用于许多实际感兴趣的子模块函数，包括与集合覆盖，匹配和设施位置相关的函数。我们提出了两个特殊的情况下的Min-Sum Submodular 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+\epsilon)$-approximate solution in time $O(n^3\log(n/\epsilon))$, 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.