Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 2019 | public
Journal Article Open

Competitive Online Optimization under Inventory Constraints


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.

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.

Attached Files

Submitted - 1901.09161.pdf


Files (356.5 kB)
Name Size Download all
356.5 kB Preview Download

Additional details

August 22, 2023
September 11, 2023