2018/09/06 by Alessandro Arlotto, Xinchang Xie, Arlotto, Alessandro +1 · 1 citation
Business, Management and Accounting · Computer Science · Decision Sciences · Mathematics · #60C05 #68W27 #68W40 #90C27 (Secondary) #90C39 (Primary) #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #Probability (math.PR) #Supply Chain and Inventory Management #cs.DM #cs.DS #math.OC #math.PR #msc:60C05 #msc:68W27 #msc:68W40 #msc:90C27 #msc:90C39
paper · pdf · doi:10.48550/arxiv.1809.02016
33 pages, 2 figures
openalex publication_date 2018/09/06 · openalex created_date 2019/06/27 · arxiv created 2019/10/28 · arxiv updated 2019/10/29 · openalex updated_date 2026/07/28
We study a dynamic and stochastic knapsack problem in which a decision maker is sequentially presented with items arriving according to a Bernoulli process over n discrete time periods. Items have equal rewards and independent weights that are drawn from a known non-negative continuous distribution F. The decision maker seeks to maximize the expected total reward of the items that she includes in the knapsack while satisfying a capacity constraint and while making terminal decisions as soon as each item weight is revealed. Under mild regularity conditions on the weight distribution F, we prove that the regret---the expected difference between the performance of the best sequential algorithm and that of a prophet who sees all of the weights before making any decision---is, at most, logarithmic in n. Our proof is constructive. We devise a reoptimized heuristic that achieves this regret bound.