Competitive Online Optimization under Inventory Constraints
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.
Additional Information
© 2019 held by the owner/author(s).Attached Files
Published - p35-lin.pdf
Files
Name | Size | Download all |
---|---|---|
md5:330495e9e19c436ab66bab8e48a2e657
|
993.7 kB | Preview Download |
Additional details
- Eprint ID
- 97032
- Resolver ID
- CaltechAUTHORS:20190710-131506895
- Created
-
2019-07-10Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field