A Caltech Library Service

Competitive Online Optimization under Inventory Constraints

Lin, Qiulin and Yi, Hanling and Pang, John and Chen, Minghua and Wierman, Adam and Honig, Michael and Xiao, Yuanzhang (2019) Competitive Online Optimization under Inventory Constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3 (1). Art. No. 10. ISSN 2476-1249.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 minimal 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-of-the-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, the CR-Pursuit algorithm achieves a competitive ratio that is within a small additive constant (i.e., 1/3) to the lower bound of ln 0+1, where 0 is the ratio between the maximum and minimum base prices.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper ItemConference Paper ItemJournal Article
Pang, John0000-0002-6485-7922
Additional Information:© 2019 Association for Computing Machinery. We acknowledge the support received from Hong Kong University Grants Committee Theme-based Research Scheme Project No. T23-407/13-N and Collaborative Research Fund No. C7036-15G, NSF grant AST-134338, NSF AitF-1637598, NSF CNS-1518941, and NSF CPS-154471. In particular, John Pang wants to acknowledge the support from ASTAR, Singapore.
Funding AgencyGrant Number
Hong Kong University Grants CommitteeT23-407/13-N
Hong Kong University Grants CommitteeC7036-15G
Agency for Science, Technology and Research (A*STAR)UNSPECIFIED
Subject Keywords:Inventory Constraints; Revenue Maximization; Online Algorithms; One-way Trading; Price Elasticity
Issue or Number:1
Record Number:CaltechAUTHORS:20190326-093440485
Persistent URL:
Official Citation:Qiulin Lin, Hanling Yi, John Pang, Minghua Chen, Adam Wierman, Michael Honig, and Yuanzhang Xiao. 2019. Competitive Online Optimization under Inventory Constraints. Proc. ACM Meas. Anal. Comput. Syst. 3, 1, Article 10 (March 2019), 28 pages.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94141
Deposited By: Tony Diaz
Deposited On:26 Mar 2019 16:53
Last Modified:19 Dec 2019 00:11

Repository Staff Only: item control page