Competitive online optimization under inventory constraints

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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)
Title of host publicationSIGMETRICS Performance 2019 - Abstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems
PublisherAssociation for Computing Machinery, Inc
Pages35-36
Number of pages2
ISBN (Electronic)9781450366786
DOIs
StatePublished - Jun 20 2019
Event14th Joint Conference of International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2019 and IFIP Performance Conference 2019, SIGMETRICS/Performance 2019 - Phoenix, United States
Duration: Jun 24 2019Jun 28 2019

Publication series

NameSIGMETRICS Performance 2019 - Abstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems

Conference

Conference14th Joint Conference of International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2019 and IFIP Performance Conference 2019, SIGMETRICS/Performance 2019
CountryUnited States
CityPhoenix
Period6/24/196/28/19

Keywords

  • Inventory Constraints
  • One-way Trading
  • Online Algorithms
  • Price Elasticity
  • Revenue Maximization

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Competitive online optimization under inventory constraints'. Together they form a unique fingerprint.

Cite this