论文标题
相关的随机背包与一个下调物镜
Correlated Stochastic Knapsack with a Submodular Objective
论文作者
论文摘要
我们研究了子管靶功能的相关随机背包问题，并具有可选的其他约束。我们利用了子解多函数的多线性扩展，并将其与MA [操作研究的数学研究，第43（3），2018年，2018年第43（3），2018年]相关的线性约束进行了适应。然后，通过随机连续贪婪算法解决了松弛，并通过一种适合争夺解决方案的新方法（Feldman等人[FOCS 2011]）。我们获得了伪个性的时间$（1-1/\ sqrt {e}）/2 \ simeq 0.1967 $近似算法，或者没有其他额外的约束，消除了对$（1-1-1-1/\ sqrt [4]} $ sime y Inim y Une of the额外的限制，从而消除了对$（1-1-1/\ sim的改进）的需求。等。 [AAAI 2019]。
We study the correlated stochastic knapsack problem of a submodular target function, with optional additional constraints. We utilize the multilinear extension of submodular function, and bundle it with an adaptation of the relaxed linear constraints from Ma [Mathematics of Operations Research, Volume 43(3), 2018] on correlated stochastic knapsack problem. The relaxation is then solved by the stochastic continuous greedy algorithm, and rounded by a novel method to fit the contention resolution scheme (Feldman et al. [FOCS 2011]). We obtain a pseudo-polynomial time $(1 - 1/\sqrt{e})/2 \simeq 0.1967$ approximation algorithm with or without those additional constraints, eliminating the need of a key assumption and improving on the $(1 - 1/\sqrt[4]{e})/2 \simeq 0.1106$ approximation by Fukunaga et al. [AAAI 2019].
