Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations
成果类型：
Article
署名作者：
Bray, Robert L.
署名单位：
Northwestern University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2022.0036
发表日期：
2025
页码：
2188-2203
关键词：
摘要：
I use empirical processes to study how the shadow prices of a linear program that allocates an endowment of nf3 is an element of Rm resources to n customers behave as n -> infinity. I show the shadow prices (i) adhere to a concentration of measure, (ii) converge to a multivariate normal under central-limit-theorem scaling, and (iii) have a variance that decreases like Theta(1/n). I use these results to prove that the expected regret in an online linear program is Theta(log n), both when the customer variable distribution is known upfront and must be learned on the fly. This result tightens the sharpest known upper bound from O(logn log log n) to O(log n) , and it extends the ohm(log n) lower bound known for single-dimensional problems to the multidimensional setting. I illustrate my new techniques with a simple analysis of a multisecretary problem.