CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20190326-093440485

[img] PDF - Submitted Version
See Usage Policy.

348Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190326-093440485

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 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
https://doi.org/10.1145/3322205.3311081DOIArticle
https://dl.acm.org/citation.cfm?id=3311081PublisherArticle
https://arxiv.org/abs/1901.09161arXivDiscussion Paper
http://resolver.caltech.edu/CaltechAUTHORS:20190710-131506895Related ItemConference Paper
https://resolver.caltech.edu/CaltechAUTHORS:20191218-160755746Related ItemJournal Article
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
Hong Kong University Grants CommitteeT23-407/13-N
Hong Kong University Grants CommitteeC7036-15G
NSFAST-134338
NSFAitF-1637598
NSFCNS-1518941
NSFCPS-154471
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:https://resolver.caltech.edu/CaltechAUTHORS:20190326-093440485
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. https://doi.org/10.1145/3311081
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94141
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:26 Mar 2019 16:53
Last Modified:19 Dec 2019 00:11

Repository Staff Only: item control page