In a typical online resource allocation problem, we start with a fixed inventory of resources and make online allocation decisions in response to resource requests that arrive sequentially over a finite horizon. We consider settings where the inventory is replenished over time according to an unknown exogenous process. We introduce black-box methods that extend any existing algorithm, originally designed without considering replenishment, into one that works with an arbitrary (adversarial or stochastic) replenishment process and asymptotically retains the competitive ratio for sufficiently large starting inventory. Our proofs rely only on properties of the general problem formulation, allowing seamless integration of exogenous replenishment into a large body of existing algorithmic results for both adversarial and stochastic arrival models.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation

  • Suho Kang,
  • Ziyang Liu,
  • Rajan Udwani

摘要

In a typical online resource allocation problem, we start with a fixed inventory of resources and make online allocation decisions in response to resource requests that arrive sequentially over a finite horizon. We consider settings where the inventory is replenished over time according to an unknown exogenous process. We introduce black-box methods that extend any existing algorithm, originally designed without considering replenishment, into one that works with an arbitrary (adversarial or stochastic) replenishment process and asymptotically retains the competitive ratio for sufficiently large starting inventory. Our proofs rely only on properties of the general problem formulation, allowing seamless integration of exogenous replenishment into a large body of existing algorithmic results for both adversarial and stochastic arrival models.