Pith. sign in

REVIEW 7 minor 32 references

Constant-Factor Algorithms for Revenue Management with Consecutive Stays

T0 review · 0 major / 7 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Consecutive-stay revenue management admits polynomial-time policies with constant-factor guarantees against the optimal online algorithm: 1−1/e for accept-or-reject and 1/4 for customer choice under Bernoulli arrivals.

desk verdict Solid paper that delivers the first constant-factor approximations against the online optimum for consecutive-stays revenue management; the proofs check out, with only minor presentation issues. read the letter →

arxiv 2506.00909 v3 pith:NKJLNHWY submitted 2025-06-01 econ.TH cs.DSmath.OC

Ming Hu , Tongwen Wu This is my paper
classification econ.THcs.DSmath.OC MSC 68W2790B50
keywords networkrevenuemanagementconsecutivestaysonlineoptimumphilosopherinequalityproposal-discardingalgorithmbasicattractionmodelassortmentoptimizationapproximationratio
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that network revenue management with consecutive stays — requests for contiguous blocks of slots on a single resource, as in railway seat sales and hotel room bookings — admits polynomial-time policies whose expected revenue is a constant fraction of the optimal online policy's revenue, with the constant independent of the maximum stay length L. Under Bernoulli arrivals, the fractions are 1−1/e ≈ 0.632 for the accept-or-reject scenario and 1/4 for the customer-choice (BAM) scenario; under general random request types both fractions lose an additional factor of 1−1/e, giving (1−1/e)² ≈ 0.399 and (1/4)(1−1/e) ≈ 0.158. These are the first constant-factor guarantees for these problems measured against the online optimum, in contrast to prior nonconstant ratios such as O(log log L/log L) or Ω(1/L) that were measured against the offline optimum — a benchmark so strong that constants are provably impossible even for a single resource. If the results stand, a booking platform can implement a simple polynomial-time rule and be guaranteed a fixed fraction of the revenue of a clairvoyant policy that knows the demand distribution but not its realizations, matching in the basic scenario the best known offline approximation ratio.

What carries the argument

The argument runs on four interlocking pieces. First, the consecutive-stays assumption compresses each resource's state into its maximal sequences of available slots — at most O(N²) per resource — and the value function decomposes additively over these sequences, yielding a polynomial-time optimal dynamic program for a single resource and the state representation for all that follows. Second, a fluid relaxation (a linear program, or a sales-based linear program for the choice scenario) upper-bounds the online optimum through a constraint that allocation probabilities cannot exceed availability probability times arrival probability — a constraint online policies satisfy but the offline optimum does not. Third, the algorithms adapt the proposal-discarding framework: each resource independently proposes to serve the arriving request with probabilities read off the fluid solution, the platform selects the highest-revenue proposal (or the revenue-maximizing assortment of proposers), and unselected proposers are discarded through a virtual resource status that marks slots unavailable even when physically free, which preserves probabilistic independence across resources. Fourth, for general arrivals, attenuation factors — offering the assortment to a given customer type only with a prescribed probability — together with a two-dimensional coupling subroutine restore independence at the cost of an extra factor 1−1/e, converted into the final bounds by the correlation-gap lemma and the separable-assignment inequality.

What would settle it

Compute the exact online optimum by dynamic programming on small exhaustive instances (for example, up to 3 resources, 4 slots, and 25 periods under Bernoulli arrivals) and simulate Algorithms 1 and 2 on the same instances; a single instance where Algorithm 1 earns less than (1−1/e)·V(I) or Algorithm 2 earns less than 0.25·V(I) would refute Theorems 1 and 2, and the same test on Algorithm 3 would test the general-arrival constants. Independently, recompute the paper's own integrality-gap constructions, which should yield V(I)/LP(I) ≈ 0.8134 in the L=2 example and V(I)/SBLP(I) ≈ 0.7941 in the BAM example; values far from these would signal an error in the examples.

Watch

Extended reading notes

Core claim

The paper establishes, through four theorems, that constant-factor approximation ratios against the optimal online algorithm are achievable in polynomial time for network revenue management with consecutive stays. In the accept-or-reject scenario under Bernoulli arrivals, the proposal-discarding policy achieves 1−1/e of the online optimum, and the paper complements this with a gap-preserving reduction from MAX-3SAT showing that even the offline version is NP-hard to approximate within 0.95+ε, while the 1−1/e bound is tight for the algorithm and matches the best known offline approximation for interval scheduling. In the BAM-based scenario, where the platform offers an assortment and the customer chooses under the basic attraction model, a sales-based fluid relaxation plus a randomized coupling subroutine yields a 1/4 guarantee. When request types are themselves random, the same machinery with attenuation factors yields (1/4)(1−1/e) for the BAM scenario and (1−1/e)² for the accept-or-reject scenario. The authors present these as the first constant-factor guarantees for the consecutive-stays structure, explicitly benchmarked against the online optimum because the offline optimum cannot sustain constants.

Load-bearing premise

The entire construction rests on the consecutive-stays assumption: every request must want one contiguous block of slots on a single resource, and if a request could consume scattered slots or span several resources, the compact state representation and the decomposition property collapse, leaving the paper with no constant-factor claim.

Editorial extensions

If this is right

  • A platform running the accept-or-reject policy is guaranteed at least 1−1/e ≈ 63.2% of the optimal online policy's expected revenue, the same ratio as the best known offline approximation for interval scheduling, so worst-case online uncertainty costs nothing at the level of the ratio.
  • The 1−1/e ratio is tight for the algorithm, and since the offline version is NP-hard to approximate within 0.95+ε, any further improvement would likely require a better offline approximation first.
  • With customer choice under BAM, the guaranteed fraction falls to 1/4 with fixed request types and to (1/4)(1−1/e) ≈ 15.8% with random request types, quantifying the revenue cost of choice and type uncertainty.
  • The fluid relaxations used for the upper bounds are not tight — integrality gaps of at most 0.8134 for the accept-or-reject LP and 0.7941 for the BAM SBLP — so the gap between the algorithms and their upper bounds is an explicit open target.
  • Under general arrivals the random type structure costs exactly one extra factor 1−1/e in both scenarios, giving (1−1/e)² ≈ 39.9% for accept-or-reject and 15.8% for BAM.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The enabling move is the benchmark choice itself — the online optimum is not a weaker consolation prize but the only benchmark on which constant-factor results for this problem class can live, because a single-resource lower bound rules out constants against the offline optimum; papers that insist on the offline benchmark should expect stay-length-dependent losses no matter the algorithm.
  • The machinery is not obviously tied to intervals — any resource-requirement structure whose state space consists of polynomially many 'maximal components' with an additive decomposition (laminar or path-shaped requests, for example) is a plausible candidate for the same proposal-discarding-plus-coupling argument, and testing that is a natural next step.
  • The attenuation mechanism puts a worst-case price on type heterogeneity — random stay lengths cost exactly a factor 1−1/e — suggesting that demand forecasting and stay-segmentation are worth roughly that factor of revenue in practice.
  • The coupling subroutines are reusable primitives — any platform that must translate intended choice probabilities into independent per-resource state transitions could adopt them without the rest of the revenue-management machinery.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 7 minor

Summary. The paper studies network revenue management with consecutive stays, where each request requires a contiguous interval of slots on a single resource. It considers two scenarios: accept-or-reject, and a BAM-based assortment setting with customer choice. For Bernoulli arrivals, it develops polynomial-time policies with approximation ratios of 1-1/e and 1/4 relative to the optimal online policy; for general arrivals, it obtains (1-1/e)^2 and (1/4)(1-1/e). The proofs are built on fluid relaxations (LP and SBLP), a decomposable state representation via maximal sequences, a proposal-discarding mechanism with virtual resource statuses, and coupling arguments. The paper also proves an offline NP-hardness bound of 0.95+epsilon and gives integrality-gap examples.

Significance. If correct, this is the first constant-factor approximation framework for this class of NRM problems when benchmarked against the online optimum, a meaningful advance over the prior nonconstant, L-dependent guarantees. The constants are explicit and parameter-free, the fluid relaxations are derived from necessary conditions of online policies rather than fitted, and the proof chain is largely self-contained. The consecutive-stays assumption is the key modeling restriction that makes the state-space compression and the decomposable property possible; the results do not extend to arbitrary slot subsets or multi-resource requests. The paper also contributes the first integration of a choice model into the proposal-discarding framework.

minor comments (7)
  1. [Abstract] The abstract reports 0.156 for the BAM-based scenario under general arrivals, but 1/4*(1-1/e) is approximately 0.158; please correct the rounding.
  2. [EC.4.2, Algorithm 5] Line 8 of Algorithm 5 can overwrite k_j with a later type when an earlier X for the same resource was already 1, contradicting the earliest-success rule stated in (EC.6) and the coupling described in the text; the pseudocode should add the guard 'if k_j=0' before assigning k_j.
  3. [EC.2.2, Proof of Proposition 3] The assertion that an optimal solution 'must still assign each θ_i' is not immediate and needs a short justification; one can assign a skipped variable request to the literal resource that currently serves fewer clause requests, losing at most c_i/2 clause revenue while gaining c_i/2 variable revenue, so there is an optimal solution with all variable requests assigned.
  4. [Section 5, Algorithm 1 and Algorithms 2-3] The proposal probabilities divide by p_t (or p_t^(k)); for periods or types with zero arrival probability, the convention that the proposal probability is zero should be stated explicitly.
  5. [Section 6, Proof of Theorem 2] The derivation of the unconditional expected revenue from the conditional bounds (14)-(15) silently multiplies by p_t; please make this multiplication explicit so the reader can follow the transition from conditional revenue to E[revenue in period t].
  6. [EC.3.3, Proof of Lemma 5] The statement that at the minimum the two terms inside the maximum must be equal is correct but terse; a one-sentence justification (if one term were larger, shifting probability mass would reduce the maximum) would improve readability.
  7. [EC.3.2, Algorithm 4] In line 6 of Algorithm 4, the expression (q_j-z_j)/(1-z_j) is undefined when z_j=1; this case is handled implicitly by the coupling, but the 0/0 convention should be stated.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the constant-factor approximation proofs are self-contained against the online-optimum benchmark, with all constants inherited from external analytic lemmas and no load-bearing self-citations.

full rationale

The derivation chain is not circular. The upper bounds V(I) ≤ LP(I) (Lemma 2) and V(I) ≤ SBLP(I) (Lemmas 4 and 7) are obtained by taking the expectation of any feasible online policy and verifying that the induced variables satisfy the LP constraints; this is a standard necessary-condition argument that does not assume the target approximation result. The proposal probabilities are defined directly from the LP/SBLP solution, and the performance analysis compares realized revenue with the LP objective using external correlation-gap and coupling inequalities (Lemma 3 from Agrawal et al. 2010; Lemma 9 from Fleischer et al. 2011; Lemma 5 proved by elementary calculus in the appendix). No parameter is fitted to a subset of data and then reported as a prediction: the fluid relaxations are solved from the instance, and every constant (1−1/e, 1/4, (1−1/e)^2, (1/4)(1−1/e)) emerges from analytic inequalities rather than from the benchmark value. The paper contains no load-bearing self-citations: the reference list includes no prior work by the authors Hu and Wu, and the cited proposal-discarding framework, sales-based linear program, correlation gap, and inapproximability results are external tools used as ingredients, not substitutes for the proof. The consecutive-stays restriction is a modeling assumption that defines the problem class, not a hidden reuse of the conclusion; the algorithms and bounds are stated for that class and benchmarked against the online optimum within the same class. The small numerical discrepancy in the abstract (0.156 versus 1/4(1−1/e) ≈ 0.158) is a rounding issue and does not indicate that any step reduces to its own input.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The only new construct is the virtual resource status, which is an algorithmic device rather than a postulated physical entity. All analytical tools are standard prior results; no free parameters are fitted.

assumptions (6)
  • standard math Correlation gap lemma for monotone submodular functions (Agrawal et al. 2010)
    Used in Theorem 1 to lower bound the expected maximum of independent proposals.
  • standard math Fleischer et al. (2011) Lemma 2.1 for sequential allocation with probabilities summing to at most 1
    Used in Lemma 8 to bound the revenue loss from attenuation in general arrivals.
  • standard math Håstad's (2001) inapproximability of MAX-3SAT
    Used in Proposition 3 to derive the 0.95+epsilon NP-hardness bound.
  • domain assumption Each request requires a contiguous interval of slots on a single resource
    Core structural assumption; enables maximal-sequence decomposition and all polynomial-time algorithms.
  • domain assumption Request arrivals are independent across periods with known probabilities (Bernoulli or general)
    Needed for the fluid LP relaxation and the online-optimum benchmark.
  • domain assumption Customer choice follows the basic attraction model (BAM), with nonnegative attractiveness weights
    Defines the BAM-based scenario and the choice probabilities used in the SBLP.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Constant-Factor Algorithms for Revenue Management with Consecutive Stays." pith.science (2026). https://pith.science/paper/NKJLNHWY

@misc{pith2026250600909,
  author       = {Pith},
  title        = {Pith review of: Constant-Factor Algorithms for Revenue Management with Consecutive Stays},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NKJLNHWY}},
  note         = {Machine review of arXiv:2506.00909}
}
read the original abstract

We study network revenue management problems motivated by applications such as railway ticket sales and hotel room bookings. Requests, each requiring a resource for a consecutive stay, arrive sequentially with known arrival probabilities. We investigate two scenarios: the accept-or-reject scenario, where a request can be fulfilled by assigning any available resource; and the BAM-based scenario, which generalizes the former by incorporating customer preferences through the basic attraction model (BAM), allowing the platform to offer an assortment of available resources from which the customer may choose. We develop polynomial-time policies and evaluate their performance using approximation ratios, defined as the ratio between the expected revenue of our policy and that of the optimal online algorithm. When each arrival has a fixed request type (e.g., the interval of the stay is fixed), we establish constant-factor guarantees: a ratio of 1 - 1/e for the accept-or-reject scenario and 0.25 for the BAM-based scenario. We further extend these results to the case where the request type is random (e.g., the interval of the stay is random). In this setting, the approximation ratios incur an additional multiplicative factor of 1 - 1/e, resulting in guarantees of at least 0.399 for the accept-or-reject scenario and 0.156 for the BAM-based scenario. These constant-factor guarantees stand in sharp contrast to the prior nonconstant competitive ratios that are benchmarked against the offline optimum.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

32 extracted references · 28 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution isbn issn journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in "" FUNCTION format.date year ...

  3. [3]

    Adelman D (2007) Dynamic bid prices in revenue management. Oper. Res. 55(4):647--661

    work page 2007

  4. [4]

    arXiv preprint arXiv:2411.08218

    AmaniHamedani A, Aouad A, Pollner T, Saberi A (2024) Improved approximations for stationary bipartite matching: Beyond probabilistic independence. arXiv preprint arXiv:2411.08218

    arXiv 2024

  5. [5]

    Aouad A, Sar ta c O (2022) Dynamic stochastic matching under limited time. Oper. Res. 70(4):2349--2383

    work page 2022

  6. [6]

    Baek J, Ma W (2022) Bifurcating constraints to improve approximation ratios for network revenue management with reusable resources. Oper. Res. 70(4):2226--2236

    work page 2022

  7. [7]

    Bertsimas D, Popescu I (2003) Revenue management in a dynamic network environment. Transp. Sci. 37(3):257--277

    work page 2003

  8. [8]

    Braverman M, Derakhshan M, Molina Lovett A (2022) Max-weight online stochastic matching: Improved approximations against the online benchmark. Proc. 23rd ACM Conf. Econ. Comput., 967--985

    work page 2022

Show all 32 references
  1. [9]

    Braverman M, Derakhshan M, Pollner T, Saberi A, Wajc D (2025) New philosopher inequalities for online B ayesian matching, via pivotal sampling. Proc. 2025 ACM-SIAM Symp. Discrete Algorithms (SODA), 3029--3068 (SIAM)

    2025

  2. [10]

    Bumpensanti P, Wang H (2020) A re-solving heuristic with uniformly bounded loss for network revenue management. Manage. Sci. 66(7):2993--3009

    2020

  3. [11]

    Fleischer L, Goemans MX, Mirrokni VS, Sviridenko M (2011) Tight approximation algorithms for maximum separable assignment problems. Math. Oper. Res. 36(3):416--431

    2011

  4. [12]

    Gallego G, Ratliff R, Shebalov S (2015) A general attraction model and sales-based linear program for network revenue management under customer choice. Oper. Res. 63(1):212--232

    2015

  5. [13]

    Gallego G, Topaloglu H (2019) Revenue M anagement and P ricing A nalytics , volume 209 (Springer)

    2019

  6. [14]

    Gallego G, Van Ryzin G (1997) A multiproduct dynamic pricing problem and its applications to network yield management. Oper. Res. 45(1):24--41

    1997

  7. [15]

    Accessed: 2025-04-03

    GlobeNewswire (2025) Railroads industry report 2025: High-speed rail and electrification trends drive railroads market growth, projected to hit \ 781.2 billion by 2030. Accessed: 2025-04-03

    2025

  8. [16]

    Jasin S, Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Math. Oper. Res. 37(2):313--345

    2012

  9. [17]

    Jasin S, Kumar S (2013) Analysis of deterministic LP -based booking limit and bid price controls for revenue management. Oper. Res. 61(6):1312--1320

    2013

  10. [18]

    Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd ACM Symp. Theory Comput. (STOC), 352--358

    1990

  11. [19]

    Kessel K, Shameli A, Saberi A, Wajc D (2022) The stationary prophet inequality problem. Proc. 23rd ACM Conf. Econ. Comput., 243--244

    2022

  12. [20]

    Luce RD (1959) Individual Choice Behavior, volume 4 (Wiley New York)

    1959

  13. [21]

    Tutorials in Oper

    Ma W (2024) Randomized rounding approaches to online allocation, sequencing, and matching. Tutorials in Oper. Res.: Smarter Decisions for a Better World, 90--116 (INFORMS)

    2024

  14. [22]

    arXiv preprint arXiv:2403.05378

    Ma W, MacRury C, Zhang J (2024) Online contention resolution schemes for network revenue management and combinatorial auctions. arXiv preprint arXiv:2403.05378

    2024 arXiv

  15. [23]

    Ma Y, Rusmevichientong P, Sumida M, Topaloglu H (2020) An approximation algorithm for network revenue management under nonstationary arrivals. Oper. Res. 68(3):834--855

    2020

  16. [24]

    (2013) Online matching and ad allocation

    Mehta A, et al. (2013) Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4):265--368

    2013

  17. [25]

    Naor J, Srinivasan A, Wajc D (2025) Online dependent rounding schemes for bipartite matchings, with. Proc. 2025 ACM-SIAM Symp. Discrete Algorithms (SODA), 3116--3154 (SIAM)

    2025

  18. [26]

    Papadimitriou C, Pollner T, Saberi A, Wajc D (2021) Online stochastic max-weight bipartite matching: Beyond prophet inequalities. Proc. 22nd ACM Conf. Econ. Comput., 763--764

    2021

  19. [27]

    Reiman MI, Wang Q (2008) An asymptotically optimal policy for a quantity-based network revenue management problem. Math. Oper. Res. 33(2):257--282

    2008

  20. [28]

    Rusmevichientong P, Sumida M, Topaloglu H, Bai Y (2023) Revenue management with heterogeneous resources: Unit resource capacities, advance bookings, and itineraries over time intervals. Oper. Res. 71(6):2196--2216

    2023

  21. [29]

    Simchi-Levi D, Zheng Z, Zhu F (2025) On greedy-like policies in online matching with reusable network resources and decaying rewards. Manage. Sci

    2025

  22. [30]

    Topaloglu H (2009) Using L agrangian relaxation to compute capacity-dependent bid prices in network revenue management. Oper. Res. 57(3):637--649

    2009

  23. [31]

    Zhang D, Adelman D (2009) An approximate dynamic programming approach to network revenue management with customer choice. Transp. Sci. 43(3):381--394

    2009

  24. [32]

    Zhu F, Liu S, Wang R, Wang Z (2023) Assign-to-seat: Dynamic capacity control for selling high-speed train tickets. Manuf. Serv. Oper. Manag. 25(3):921--938

    2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.