# Competitive Online Optimization under Inventory Constraints

arXiv: https://arxiv.org/abs/1901.09161 · HTML: https://mlsanity.com/paper/1901.09161/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2019.

## Built on by (most cited first, 4 of 4)

- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Riemannian Projection-free Online Learning](https://mlsanity.com/paper/2305.19349/) (2023)
- [Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints](https://mlsanity.com/paper/2212.01689/) (2022)
- [A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives](https://mlsanity.com/paper/2406.03574/) (2024)

## Abstract (arXiv)

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, textsfCR-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 textsfCR-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.