论文标题
最低成本自适应下覆盖
Minimum Cost Adaptive Submodular Cover
论文作者
论文摘要
自适应次数是随机优化的一个基本概念，具有许多应用，例如传感器放置，假设识别和病毒营销。我们考虑了自适应解换功能的最低成本覆盖率的问题，并提供了$ 4（1+ \ ln Q）$ - 近似算法的问题，其中$ q $是目标值。实际上，我们认为将覆盖范围成本的$ p^{th} $时刻降至最低的一个更一般的目标，并表明我们的算法同时实现了$（p+1）^{p+1} \ cdot（\ ln q+1）^p $近似保证，用于所有$ p \ ge ge ge 1 $ $ 1 $。我们所有的近似值率最好是恒定因素（假设$ p \ ne np $）。此外，我们的结果还扩展到要覆盖{\ em protern}自适应解码功能的设置。最后，我们评估了算法在假设鉴定实例上的经验性能。
Adaptive submodularity is a fundamental concept in stochastic optimization, with numerous applications such as sensor placement, hypothesis identification and viral marketing. We consider the problem of minimum cost cover of adaptive-submodular functions, and provide a $4(1+\ln Q)$-approximation algorithm, where $Q$ is the goal value. In fact, we consider a significantly more general objective of minimizing the $p^{th}$ moment of the coverage cost, and show that our algorithm simultaneously achieves a $(p+1)^{p+1}\cdot (\ln Q+1)^p$ approximation guarantee for all $p\ge 1$. All our approximation ratios are best possible up to constant factors (assuming $P\ne NP$). Moreover, our results also extend to the setting where one wants to cover {\em multiple} adaptive-submodular functions. Finally, we evaluate the empirical performance of our algorithm on instances of hypothesis identification.
