论文标题
Min-sum suppodular覆盖问题的本地搜索算法
A Local Search Algorithm for the Min-Sum Submodular Cover Problem
论文作者
论文摘要
我们考虑使用本地搜索解决Min-sum subsodular覆盖问题的问题。 Min-sum supdoular覆盖问题概括了NP完整的Min-sum设置盖问题，用单调的子模具集函数代替了输入集封面实例。一种简单的贪婪算法达到了4个近似因子，除非p = np [Streeter和Golovin，Neurips，neurips，2008年]。我们通过分析局部搜索算法来补充贪婪的算法。基于Munagala等人的工作。 [ICDT，2005]，我们表明，使用简单的初始化，直接的本地搜索算法可以在时间$ o（n^3 \ log（n/ε））$中实现$（4+ε）$ - 近似解决方案，前提是单调子模量集也是二阶Supermodular。已显示二阶超模型可用于许多实际感兴趣的子模块化功能，包括与设置覆盖，匹配和设施位置相关的功能。我们介绍了两种特殊情况的Min-sum supdoular覆盖物的实验，并发现本地搜索算法可以优于小型数据集的贪婪算法。
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^3\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.
