Competitive Online Optimization under Inventory Constraints

Qiulin Lin, Hanling Yi, John Pang, Minghua Chen, Adam Wierman, Michael Honig, Yuanzhang Xiao

Research output: Contribution to journalArticlepeer-review

Abstract

This paper studies online optimization under inventory (budget) constraints. While online optimization is a well-studied topic, versions with inventory constraints have proven difficult. We consider a formulation of inventory-constrained optimization that is a generalization of the classic one-way trading problem and has a wide range of applications. We present a new algorithmic framework, CR-Pursuit, and prove that it achieves the optimal competitive ratio among all deterministic algorithms (up to a problem-dependent constant factor) for inventory-constrained online optimization. Our algorithm and its analysis not only simplify and unify the state-ofthe-art results for the standard one-way trading problem, but they also establish novel bounds for generalizations including concave revenue functions. For example, for one-way trading with price elasticity, CR-Pursuit achieves a competitive ratio within a small additive constant (i.e., 1/3) to the lower bound of ln θ + 1, where θ is the ratio between the maximum and minimum base prices.

Original languageEnglish (US)
Pages (from-to)35-36
Number of pages2
JournalPerformance Evaluation Review
Volume47
Issue number1
DOIs
StatePublished - Dec 17 2019

Keywords

  • inventory constraints
  • one-way trading
  • online algorithms
  • price elasticity
  • revenue maximization

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Competitive Online Optimization under Inventory Constraints'. Together they form a unique fingerprint.

Cite this