Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack.

Jiashuo Jiang Will Ma Jiawei Zhang

Published in: SODA (2022)

Keyphrases

multi unit
upper bound
lower bound
worst case
combinatorial auctions
dynamic programming
sufficient conditions
objective function
evolutionary algorithm
np hard
monte carlo
knapsack problem
packing problem
budget constraints