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. doi:10.1145/3309697.3331495. https://resolver.caltech.edu/CaltechAUTHORS:20191218-160755746
![]() |
PDF
- Published Version
See Usage Policy. 576kB |
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: |
| ||||||||||||
ORCID: |
| ||||||||||||
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 | ||||||||||||
DOI: | 10.1145/3309697.3331495 | ||||||||||||
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: | 16 Nov 2021 17:53 |
Repository Staff Only: item control page