# A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2018.

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

- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Online Resource Allocation under Horizon Uncertainty](https://mlsanity.com/paper/2206.13606/) (2022)
- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Stateful Offline Contextual Policy Evaluation and Learning](https://mlsanity.com/paper/2110.10081/) (2021)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Online Pricing and Allocation with Demand Learning and Fulfillment Cost](https://mlsanity.com/paper/2501.18049/) (2025)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Dynamic Budget Throttling in Repeated Second-Price Auctions](https://mlsanity.com/paper/2207.04690/) (2022)
- [Demand Balancing in Primal-Dual Optimization for Blind Network Revenue Management](https://mlsanity.com/paper/2404.04467/) (2024)
- [A Re-solving Heuristic for Dynamic Assortment Optimization with Knapsack Constraints](https://mlsanity.com/paper/2407.05564/) (2024)
- [Episodic Contextual Bandits with Knapsacks under Conversion Models](https://mlsanity.com/paper/2507.06859/) (2025)
- [Non-Stationary Online Resource Allocation: Learning from a Single Sample](https://mlsanity.com/paper/2602.18114/) (2026)
- [Adaptive Resolving Methods for Markov Decision Processes with Function Approximations](https://mlsanity.com/paper/2505.12037/) (2025)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026)
- [A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret](https://mlsanity.com/paper/2609.05895/) (2026)
- [Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving](https://mlsanity.com/paper/2609.28263/) (2026)

## Abstract (arXiv)

We consider the canonical (quantity-based) network revenue management problem, where a firm accepts or rejects incoming customer requests irrevocably in order to maximize expected revenue given limited resources. Due to the curse of dimensionality, the exact solution to this problem by dynamic programming is intractable when the number of resources is large. We study a family of re-solving heuristics that periodically re-optimize an approximation to the original problem known as the deterministic linear program (DLP), where random customer arrivals are replaced by their expectations. We find that, in general, frequently re-solving the DLP produces the same order of revenue loss as one would get without re-solving, which scales as the square root of the time horizon length and resource capacities. By re-solving the DLP at a few selected points in time and applying thresholds to the customer acceptance probabilities, we design a new re-solving heuristic whose revenue loss is uniformly bounded by a constant that is independent of the time horizon and resource capacities.