Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations: The Optimal Online Policy's Expected Regret Grows at Least Logarithmically in the HorizonResearch Paper
In an online linear program, customers arrive one at a time and a firm must accept or reject each one at once, spending a shared inventory of resources. The model covers network revenue management, ad allocation and order fulfilment (Li and Ye, 2022). Its central performance measure is the regret: the gap between what an omniscient planner collects and…