论文标题
您希望如何贪婪：同时或重复？
How Do You Want Your Greedy: Simultaneous or Repeated?
论文作者
论文摘要
我们提出同时播放的，这是一种确定性算法，用于受约束的下管最大化。在高水平上，该算法维护$ \ ell $解决方案，并以同时的方式贪婪地更新它们。同时播放的$ k $ - 延伸系统和更通用的$ k $ - systems，即$（k + 1）^2/k = k + k + \ m athcal {o}（1）$和$（1 + \ sqrt {k + 2}） \ Mathcal {o}（\ sqrt {k}）$。这与以前的算法相反，后者旨在在一种情况下提供紧密的近似保证，但并非两者兼而有之。我们还改进了对重复的分析，表明它的近似值为$ k + \ \ \ \ \ \ \ \ \ sqrt {k}）$，对于$ k $ - systems，当允许使用$ \ nathcal {o}（\ sqrt {k}）$ iTERES和以前的分析时，允许$ k $ -Systems进行运行。我们证明，这两种算法都可以在几乎线性的时间内进行修改，并在近似值中任意损失。 同时播放和重复进行的既有灵活性都足以纳入$ m $额外的背包约束，同时保留了相似的近似保证：这两种算法都产生了大约$ k + k + k + k + 2m + \ 2m + \ nathcal {o}（o}（\ sqrt {k + m m} $ $ k $的近似保证，以供应$ K + m} $ - $ k $ ssedem $ k $ - $ K + 2M + \ Mathcal {O}（\ sqrt {M}）$的近似保证对于$ K $ - 延伸系统。为了补充我们的算法贡献，我们提供了一个硬度结果，该结果指出，没有算法使多个甲骨文的查询可以更好地实现大于$ K + 1/2 + \ varepsilon $。我们还提出了supdulargreedy.jl，这是一个实现这些算法的朱莉娅软件包，可以在https://github.com/crharshaw/submodulargreedy.jl上下载。最后，我们测试这些算法在实际数据集上的有效性。
We present SimultaneousGreedys, a deterministic algorithm for constrained submodular maximization. At a high level, the algorithm maintains $\ell$ solutions and greedily updates them in a simultaneous fashion. SimultaneousGreedys achieves the tightest known approximation guarantees for both $k$-extendible systems and the more general $k$-systems, which are $(k+1)^2/k = k + \mathcal{O}(1)$ and $(1 + \sqrt{k+2})^2 = k + \mathcal{O}(\sqrt{k})$, respectively. This is in contrast to previous algorithms, which are designed to provide tight approximation guarantees in one setting, but not both. We also improve the analysis of RepeatedGreedy, showing that it achieves an approximation ratio of $k + \mathcal{O}(\sqrt{k})$ for $k$-systems when allowed to run for $\mathcal{O}(\sqrt{k})$ iterations, an improvement in both the runtime and approximation over previous analyses. We demonstrate that both algorithms may be modified to run in nearly linear time with an arbitrarily small loss in the approximation. Both SimultaneousGreedys and RepeatedGreedy are flexible enough to incorporate the intersection of $m$ additional knapsack constraints, while retaining similar approximation guarantees: both algorithms yield an approximation guarantee of roughly $k + 2m + \mathcal{O}(\sqrt{k+m})$ for $k$-systems and SimultaneousGreedys enjoys an improved approximation guarantee of $k+2m + \mathcal{O}(\sqrt{m})$ for $k$-extendible systems. To complement our algorithmic contributions, we provide a hardness result which states that no algorithm making polynomially many oracle queries can achieve an approximation better than $k + 1/2 + \varepsilon$. We also present SubmodularGreedy.jl, a Julia package which implements these algorithms and may be downloaded at https://github.com/crharshaw/SubmodularGreedy.jl . Finally, we test the effectiveness of these algorithms on real datasets.
