CaltechAUTHORS
  A Caltech Library Service

Competitive Online Optimization under Inventory Constraints

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

[img] 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:
URLURL TypeDescription
https://doi.org/10.1145/3309697.3331495DOIArticle
http://resolver.caltech.edu/CaltechAUTHORS:20190326-093440485Related ItemJournal Article
https://resolver.caltech.edu/CaltechAUTHORS:20191218-160755746Related ItemJournal Article
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
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