Competitive Online Optimization under Inventory Constraints

• Published in: Performance evaluation review 2019-12, Vol.47 (1), p.35-36
• Main Authors: Lin, Qiulin, Yi, Hanling, Pang, John, Chen, Minghua, Wierman, Adam, Honig, Michael, Xiao, Yuanzhang
• Format: Article
• Language: English
• Subjects: Applied computing; Applied computing / Law, social and behavioral sciences; Applied computing / Law, social and behavioral sciences / Economics; Mathematics of computing; Mathematics of computing / Mathematical analysis; Mathematics of computing / Mathematical analysis / Mathematical optimization; Theory of computation; Theory of computation / Design and analysis of algorithms; Theory of computation / Design and analysis of algorithms / Online algorithms; Theory of computation / Design and analysis of algorithms / Online algorithms / Online learning algorithms; Theory of computation / Models of computation; Theory of computation / Models of computation / Interactive computation; Theory of computation / Theory and algorithms for application domains; Theory of computation / Theory and algorithms for application domains / Machine learning theory; Theory of computation / Theory and algorithms for application domains / Machine learning theory / Online learning theory
• ISSN: 0163-5999
• DOI: 10.1145/3376930.3376953

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.