论文标题
非单调酮次管的实用且可行的算法，尺寸约束
Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
论文作者
论文摘要
我们介绍了相对于尺寸约束的最大化（不一定是单调的）组合和可行的算法。我们通过具有最佳适应性和几乎最佳查询复杂性的算法提高了最佳的近似因子，至$ 0.193 - \ varepsilon $。这项工作的会议版本错误地采用了一个子例程，该子例程不适合非单调的，子模块功能。在此版本中，我们提出了一个固定且改进的子例程，以添加一个具有高平均边缘增益的集合，即ThreshSeq，该集合以$ O（\ log（n））$自适应回合返回具有高概率的解决方案。此外，我们提供两种近似算法。 The first has approximation ratio $1/6 - \varepsilon$, adaptivity $O( \log (n) )$, and query complexity $O( n \log (k) )$, while the second has approximation ratio $0.193 - \varepsilon$, adaptivity $O( \log^2 (n) )$, and query complexity $O(n \log (k))$.我们的算法经过经验验证，以使用较少数量的自适应回合和总查询，同时与最新的近似算法相比，获得具有高目标值的解决方案，包括使用多线性扩展的连续算法。
We present combinatorial and parallelizable algorithms for maximization of a submodular function, not necessarily monotone, with respect to a size constraint. We improve the best approximation factor achieved by an algorithm that has optimal adaptivity and nearly optimal query complexity to $0.193 - \varepsilon$. The conference version of this work mistakenly employed a subroutine that does not work for non-monotone, submodular functions. In this version, we propose a fixed and improved subroutine to add a set with high average marginal gain, ThreshSeq, which returns a solution in $O( \log(n) )$ adaptive rounds with high probability. Moreover, we provide two approximation algorithms. The first has approximation ratio $1/6 - \varepsilon$, adaptivity $O( \log (n) )$, and query complexity $O( n \log (k) )$, while the second has approximation ratio $0.193 - \varepsilon$, adaptivity $O( \log^2 (n) )$, and query complexity $O(n \log (k))$. Our algorithms are empirically validated to use a low number of adaptive rounds and total queries while obtaining solutions with high objective value in comparison with state-of-the-art approximation algorithms, including continuous algorithms that use the multilinear extension.
