Competitive Online Optimization under Inventory Constraints

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations

Author(s)

  • Qiulin Lin
  • Hanling Yi
  • John Pang
  • Adam Wierman
  • Michael Honig
  • Yuanzhang Xiao

Detail(s)

Original languageEnglish
Pages (from-to)35-36
Journal / PublicationPerformance Evaluation Review
Volume47
Issue number1
Publication statusPublished - Jun 2019
Externally publishedYes

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.

Research Area(s)

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

Bibliographic Note

The publication is also published in SIGMETRICS '19.

Citation Format(s)

Competitive Online Optimization under Inventory Constraints. / Lin, Qiulin; Yi, Hanling; Pang, John; Chen, Minghua; Wierman, Adam; Honig, Michael; Xiao, Yuanzhang.

In: Performance Evaluation Review, Vol. 47, No. 1, 06.2019, p. 35-36.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review