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. ACM SIGMETRICS Performance Evaluation Review, 47 (1). pp. 35-36. ISSN 0163-5999. https://resolver.caltech.edu/CaltechAUTHORS:20191218-160755746

[img] PDF - Published Version
See Usage Policy.

562Kb

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

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-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, 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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/3309697.3331495DOIArticle
https://resolver.caltech.edu/CaltechAUTHORS:20190326-093440485Related ItemJournal Article
https://resolver.caltech.edu/CaltechAUTHORS:20190710-131506895Related ItemConference Paper
ORCID:
AuthorORCID
Pang, John0000-0002-6485-7922
Additional Information:© 2019 held by the owner/author(s).
Subject Keywords:Inventory Constraints; Revenue Maximization; Online Algorithms; One-way Trading; Price Elasticity
Issue or Number:1
Record Number:CaltechAUTHORS:20191218-160755746
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20191218-160755746
Official Citation:Qiulin Lin, Hanling Yi, John Pang, Minghua Chen, Adam Wierman, Michael Honig, and Yuanzhang Xiao. 2019. Competitive Online Optimization under Inventory Constraints. In ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS ’19 Abstracts), June 24–28, 2019, Phoenix, AZ, USA. ACM, New York, NY, USA, 2 pages. https://doi.org/10.1145/3309697.3331495
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100369
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:19 Dec 2019 00:17
Last Modified:04 Nov 2020 19:49

Repository Staff Only: item control page