论文标题
在几乎线性时间内，在基质上最大化的确定性近似
Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time
论文作者
论文摘要
我们研究最大化非单调的，非阴性的下管功能的问题。此问题的先前最著名的确定性近似值为$ \ frac {1} {4}-ε$在$ \ Mathcal {o}下（（（{n^4}/ε）\ log n）$ time复杂性。我们表明，在$ \ Mathcal {o}（o}（nr）$下，可以提高该确定比率为$ \ frac {1} {4} $，然后提出更实用的算法，将其配置为TwingreedyFast，可实现$ \ frac {1} {1} {4} - $确定的级别，几乎是lin-linniantial cartimio cartimio。 $ \ MATHCAL {O}（\ frac {n}ε\ log \ frac {r}ε）$。我们的方法基于一种新型算法框架，该算法框架同时通过贪婪搜索构建了两个候选解决方案集，这使我们能够通过充分利用独立系统的属性来获得改进的性能界限。作为该框架的副产品，我们还表明Twingreedyfast实现了$ \ frac {1} {2p+2}-ε$确定性比率在$ p $ -SET系统约束下具有相同的时间复杂性。为了展示我们方法的实用性，我们经验评估了Twingreedyfast在两个网络应用程序上的性能，并观察到它的表现优于最先进的确定性和随机算法，并有效地实现了我们的问题。
We study the problem of maximizing a non-monotone, non-negative submodular function subject to a matroid constraint. The prior best-known deterministic approximation ratio for this problem is $\frac{1}{4}-ε$ under $\mathcal{O}(({n^4}/ε)\log n)$ time complexity. We show that this deterministic ratio can be improved to $\frac{1}{4}$ under $\mathcal{O}(nr)$ time complexity, and then present a more practical algorithm dubbed TwinGreedyFast which achieves $\frac{1}{4}-ε$ deterministic ratio in nearly-linear running time of $\mathcal{O}(\frac{n}ε\log\frac{r}ε)$. Our approach is based on a novel algorithmic framework of simultaneously constructing two candidate solution sets through greedy search, which enables us to get improved performance bounds by fully exploiting the properties of independence systems. As a byproduct of this framework, we also show that TwinGreedyFast achieves $\frac{1}{2p+2}-ε$ deterministic ratio under a $p$-set system constraint with the same time complexity. To showcase the practicality of our approach, we empirically evaluated the performance of TwinGreedyFast on two network applications, and observed that it outperforms the state-of-the-art deterministic and randomized algorithms with efficient implementations for our problem.
