论文标题
实用预算的下管最大化
Practical Budgeted Submodular Maximization
论文作者
论文摘要
我们认为最大化非负单调的非负单调性函数的问题受到了背包约束，这也称为预算的supprodular最大化（BSM）问题。 Sviridenko（2004）表明，通过猜测最佳解决方案的3个适当元素，然后执行贪婪的算法，可以获得BSM的最佳近似值为$α= 1-1/e \约0.632 $。但是，需要猜测（通过枚举）3个元素使Sviridenko的算法不切实际，因为它会导致$ O（n^5）$的时间复杂性（可以使用Badanidiyyuru＆Vondrak（2014）的阈值技术稍微改进，但只能稍微改进，但只能大致$ O（n^4^4^4^4^4）$）。本文中我们的主要结果表明，猜测就足够了。具体而言，只要进行2个猜测，我们获得了相同的最佳近似值$α$，而时间复杂性的提高约为$ o（n^3）$。此外，通过仅做一个猜测，我们几乎获得了$ 0.6174> 0.6174>0.9767α$的好近似值，大约是$ o（n^2）$时间。 在我们的工作之前，唯一已知的算法是BSM的近似值接近$α$的算法是Sviridenko的算法和Ene＆Nguyen（2019）的算法，可实现$（α-ε）$ - 近似值。但是，Ene＆nguyen的算法需要$ {（1/ε）}^{o（1/ε^4）} n \ log^2 n $ time，因此，理论上的利益仅为$ {（1/ε）}^{o（1/ε）}^{o（1/ε^4）$ for Mempover for Mempover for Mempover Ademeper for Medimesporter ymmemoreporementer um $。相比之下，我们分析的所有算法都是简单且可行的，这使它们成为实际使用的良好候选者。 最近，Tang等人。 （2020）研究了一种简单的贪婪算法，该算法已经具有很长的研究史，并证明其近似比至少为0.405。我们对此结果有所改善，并表明该算法的近似值在[0.427，0.462]范围内。
We consider the problem of maximizing a non-negative monotone submodular function subject to a knapsack constraint, which is also known as the Budgeted Submodular Maximization (BSM) problem. Sviridenko (2004) showed that by guessing 3 appropriate elements of an optimal solution, and then executing a greedy algorithm, one can obtain the optimal approximation ratio of $α=1-1/e\approx 0.632$ for BSM. However, the need to guess (by enumeration) 3 elements makes the algorithm of Sviridenko impractical as it leads to a time complexity of $O(n^5)$ (which can be slightly improved using the thresholding technique of Badanidiyuru & Vondrak (2014), but only to roughly $O(n^4)$). Our main results in this paper show that fewer guesses suffice. Specifically, by making only 2 guesses, we get the same optimal approximation ratio of $α$ with an improved time complexity of roughly $O(n^3)$. Furthermore, by making only a single guess, we get an almost as good approximation ratio of $0.6174>0.9767α$ in roughly $O(n^2)$ time. Prior to our work, the only algorithms that were known to obtain an approximation ratio close to $α$ for BSM were the algorithm of Sviridenko and an algorithm of Ene & Nguyen (2019) that achieves $(α-ε)$-approximation. However, the algorithm of Ene & Nguyen requires ${(1/ε)}^{O(1/ε^4)}n\log^2 n$ time, and hence, is of theoretical interest only as ${(1/ε)}^{O(1/ε^4)}$ is huge even for moderate values of $ε$. In contrast, all the algorithms we analyze are simple and parallelizable, which makes them good candidates for practical use. Recently, Tang et al. (2020) studied a simple greedy algorithm that already has a long research history, and proved that its approximation ratio is at least 0.405. We improve over this result, and show that the approximation ratio of this algorithm is within the range [0.427, 0.462].
