Lin, Qiulin and Yi, Hanling and Wierman, Adam and Pang, John and Honig, Michael and Chen, Minghua and Xiao, Yuanzhang (2019) Competitive Online Optimization under Inventory Constraints. In: Abstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems. Association for Computing Machinery , New York, NY, pp. 35-36. ISBN 978-1-4503-6678-6. https://resolver.caltech.edu/CaltechAUTHORS:20190710-131506895
![]() |
PDF
- Published Version
See Usage Policy. 993kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190710-131506895
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: | Book Section | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 | ||||||||||||
DOI: | 10.1145/3309697.3331495 | ||||||||||||
Record Number: | CaltechAUTHORS:20190710-131506895 | ||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190710-131506895 | ||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
ID Code: | 97032 | ||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||
Deposited By: | Tony Diaz | ||||||||||||
Deposited On: | 10 Jul 2019 20:53 | ||||||||||||
Last Modified: | 16 Nov 2021 17:25 |
Repository Staff Only: item control page