摘要
在这项工作中,我们研究了随机预算多轮次子模最大化 (SBMSm) 问题,旨在自适应地最大化多个轮次中定义在项目子集上的单调且子模目标函数的总和。目标函数还取决于随机事件的实现,并且我们可以在所有轮次中选择的项目总数受限预算限制。这个问题扩展了并推广到多轮次设置,例如 (自适应) 影响最大化和随机探测等经过充分研究的问题。
我们证明,如果项目和随机事件的数量在某种程度上是有限的,则存在 SBMSm 的多项式时间动态规划算法。然后,我们为 SBMSm 提供了一个简单的贪心 $1/2(1-1/e-\epsilon)\approx 0.316$ 近似算法,该算法首先非自适应地分配每个轮次要花费的预算,然后使用分配给每个轮次的预算贪婪且自适应地最大化目标函数。最后,我们引入了“预算自适应差距”,通过它来衡量 SBMSm 的自适应策略比最佳部分自适应策略好多少,后者与我们的贪心算法一样,预先确定预算分配。我们证明预算自适应差距介于 $e/(e-1)\approx 1.582$ 和 $2$ 之间。