论文标题
在未知的背包约束下，用有界曲率的弯曲曲率最大化函数
Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
论文作者
论文摘要
本文研究了在未知的背包约束下最大程度地提高单调下一个函数的问题。解决此问题的解决方案是一项策略，该策略决定基于过去的包装历史记录下一步打包哪些项目。策略的鲁棒性因素是通过遵循策略获得的解决方案的最坏情况比率，也是知道背包容量的最佳解决方案。我们制定了一个具有鲁棒性因素的策略，该策略正在减少子模函数的曲率$ c $。在极端情况下，$ c = 0 $对应于添加剂目标函数，它与先前已知且最佳的鲁棒性系数匹配$ 1/2 $。对于$ c = 1 $的另一个极端情况，它产生的稳健性因子约为0.35 $，比最佳以前已知的鲁棒性系数$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \约0.06 $。 对我们的政策的分析依赖于一种贪婪的算法，这是对沃尔西（Wolsey）的贪婪算法的略有修改，该算法具有已知的knapsack限制因素。在具有曲率$ c $的子模具目标函数的情况下，我们为这两种算法获得了紧密的近似保证。
This paper studies the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop a policy with a robustness factor that is decreasing in the curvature $c$ of the submodular function. For the extreme cases $c=0$ corresponding to an additive objective function, it matches a previously known and best possible robustness factor of $1/2$. For the other extreme case of $c=1$ it yields a robustness factor of $\approx 0.35$ improving over the best previously known robustness factor of $\approx 0.06$. The analysis of our policy relies on a greedy algorithm that is a slight modification of Wolsey's greedy algorithm for the submodular knapsack problem with a known knapsack constraint. We obtain tight approximation guarantees for both of these algorithms in the setting of a submodular objective function with curvature $c$.
