Tight Guarantees for Multiunit Prophet Inequalities and Online Stochastic Knapsack
研究了多单位先知不等式和在线随机背包问题，通过线性规划刻画最优策略，得到了紧致比率，并推广到多资源场景。
In “Tight Guarantees for Multiunit Prophet Inequalities and Online Stochastic Knapsack,” Jiang, Ma, and Zhang analyze the multiunit prophet inequalities and online knapsack problems. They formulate the problems as the online contention resolution scheme problems. Then, they develop linear programming formulations to represent the online contention resolution scheme problems. They characterize the optimal solution of the linear programming and derive the corresponding optimal policies. For the multiunit prophet inequalities, they are able to obtain the tight ratios, which improved over the previous ones. For the online stochastic knapsack problem, their ratio is also optimal and the best up to date. They finally generalize their results to the multiresource setting and expand the applicability of their approach.