LLM2D
带预算的随机多轮次子模优化
Stochastic Multi-round Submodular Optimization with Budget
发布日期: 9/25/2024
arXiv ID: oai:arXiv.org:2404.13737v3

摘要

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