Submodular Maximization with Uncertain Knapsack Capacity
Submodular Maximization with Uncertain Knapsack Capacity
复制标题
背包容量不确定的子模最大化
DOI：
10.1007/978-3-319-77404-6_48
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Fukunaga Takuro
中科院分区：
文献类型：
--
作者：
Kawase Yasushi;Sumita Hanna;Fukunaga Takuro
研究了不确定背包约束下单调次模函数的最大化问题。具体来说，讨论的问题的情况下，背包容量没有明确给出，只能通过一个预言机，回答当前的解决方案是否是可行的，当一个项目被添加到解决方案中。假设最后一项溢出背包容量时允许取消，我们讨论了该问题的自适应策略的鲁棒性比，这是最坏情况下的输出解达到的目标值与最优目标值的比率。提出了鲁棒比的随机化策略和鲁棒比的确定性策略.我们还考虑了一个通用的政策，选择项目的预先计算的序列。我们提出了一个鲁棒性比$（1-1/\sqrt[4]{e}）/2$的随机通用策略。当取消是不允许的，没有随机化的自适应策略实现恒定的鲁棒性比。由于这种困难，我们假设背包容量的概率分布是给定的，我们考虑计算一个序列的项目，最大化预期的目标值。我们提出了一个多项式时间的随机算法的近似比$（1-1/\sqrt[4]{e}）/4-\sqrt $的任何小常数。
We consider the maximization problem of monotone submodular functions under an uncertain knapsack constraint. Specifically, the problem is discussed in the situation where the knapsack capacity is not given explicitly and can be accessed only through an oracle that answers whether or not the current solution is feasible when an item is added to the solution. Assuming that cancellation of the last item is allowed when it overflows the knapsack capacity, we discuss the robustness ratios of adaptive policies for this problem, which are the worst case ratios of the objective values achieved by the output solutions to the optimal objective values. We present a randomized policy of robustness ratioand a deterministic policy of robustness ratio. We also consider a universal policy that chooses items following a precomputed sequence. We present a randomized universal policy of robustness ratio $(1-1/\sqrt[4]{e})/2$. When cancellation is not allowed, no randomized adaptive policy achieves a constant robustness ratio. Because of this hardness, we assume that a probability distribution of the knapsack capacity is given, and we consider computing a sequence of items that maximizes the expected objective value. We present a polynomial time randomized algorithm of approximation ratio $(1-1/\sqrt[4]{e})/4-\epsilon$ for any small constant.