Competitive Online Optimization under Inventory Constraints
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916533565915136 |
|---|---|
| author | Lin, Qiulin Yi, Hanling Pang, John Chen, Minghua Wierman, Adam Honig, Michael Xiao, Yuanzhang |
| author_facet | Lin, Qiulin Yi, Hanling Pang, John Chen, Minghua Wierman, Adam Honig, Michael Xiao, Yuanzhang |
| contents | 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, \textsf{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 \textsf{CR-Pursuit} algorithm achieves a competitive ratio that is 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1901_09161 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Competitive Online Optimization under Inventory Constraints Lin, Qiulin Yi, Hanling Pang, John Chen, Minghua Wierman, Adam Honig, Michael Xiao, Yuanzhang Performance Data Structures and Algorithms Systems and Control Optimization and Control 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, \textsf{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 \textsf{CR-Pursuit} algorithm achieves a competitive ratio that is 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. |
| title | Competitive Online Optimization under Inventory Constraints |
| topic | Performance Data Structures and Algorithms Systems and Control Optimization and Control |
| url | https://arxiv.org/abs/1901.09161 |