# Near-Optimal Primal-Dual Algorithms for Quantity-Based Network Revenue Management

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2020.

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

- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Decoupling Learning and Decision-Making: Breaking the O(√T) Barrier in Online Resource Allocation with First-Order Methods](https://mlsanity.com/paper/2402.07108/) (2024)
- [Dynamic Budget Throttling in Repeated Second-Price Auctions](https://mlsanity.com/paper/2207.04690/) (2022)
- [Wait-Less Offline Tuning and Re-solving for Online Decision Making](https://mlsanity.com/paper/2412.09594/) (2024)
- [Online Regenerative Learning](https://mlsanity.com/paper/2209.08657/) (2022)
- [Online Linear Programming for Multi-Objective Routing in LLM Serving](https://mlsanity.com/paper/2607.03948/) (2026)
- [Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More](https://mlsanity.com/paper/2610.09577/) (2026)

## Abstract (arXiv)

We study the canonical quantity-based network revenue management (NRM) problem where the decision-maker must irrevocably accept or reject each arriving customer request with the goal of maximizing the total revenue given limited resources. The exact solution to the problem by dynamic programming is computationally intractable due to the well-known curse of dimensionality. Existing works in the literature make use of the solution to the deterministic linear program (DLP) to design asymptotically optimal algorithms. Those algorithms rely on repeatedly solving DLPs to achieve near-optimal regret bounds. It is, however, time-consuming to repeatedly compute the DLP solutions in real time, especially in large-scale problems that may involve hundreds of millions of demand units. In this paper, we propose innovative algorithms for the NRM problem that are easy to implement and do not require solving any DLPs. Our algorithm achieves a regret bound of O(log k), where k is the system size. To the best of our knowledge, this is the first NRM algorithm that (i) has an o(√k) asymptotic regret bound, and (ii) does not require solving any DLPs.