Competitive Online Optimization under Inventory Constraints
Refereed conference paper presented and published in conference proceedings

香港中文大學研究人員
替代計量分析
.

其它資訊
摘要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.
著者Qiulin Lin, Hanling Yi, John Pang, Minghua Chen, Adam Wierman, Michael Honig, Yuanzhang Xiao
會議名稱14th Joint Conference of International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2019 and IFIP Performance Conference 2019, SIGMETRICS/Performance 2019
會議開始日24.06.2019
會議完結日28.06.2019
會議地點Phoenix, Arizona
會議國家/地區美國
會議論文集題名SIGMETRICS Performance 2019 - Abstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems
出版年份2019
月份6
頁次35 - 36
國際標準書號978-145036678-6
語言英式英語

上次更新時間 2022-08-01 於 23:50