TY - GEN
T1 - Competitive online optimization under inventory constraints
AU - Lin, Qiulin
AU - Yi, Hanling
AU - Pang, John
AU - Chen, Minghua
AU - Wierman, Adam
AU - Honig, Michael
AU - Xiao, Yuanzhang
PY - 2019/6/20
Y1 - 2019/6/20
N2 - 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-ofthe- 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.
AB - 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-ofthe- 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.
KW - Inventory Constraints
KW - One-way Trading
KW - Online Algorithms
KW - Price Elasticity
KW - Revenue Maximization
UR - http://www.scopus.com/inward/record.url?scp=85069201395&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85069201395&partnerID=8YFLogxK
U2 - 10.1145/3309697.3331495
DO - 10.1145/3309697.3331495
M3 - Conference contribution
T3 - SIGMETRICS Performance 2019 - Abstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems
SP - 35
EP - 36
BT - SIGMETRICS Performance 2019 - Abstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems
PB - Association for Computing Machinery, Inc
T2 - 14th Joint Conference of International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2019 and IFIP Performance Conference 2019, SIGMETRICS/Performance 2019
Y2 - 24 June 2019 through 28 June 2019
ER -