pith. sign in

arxiv: 2605.25888 · v1 · pith:ZNJXCRYInew · submitted 2026-05-25 · 💻 cs.LG · math.OC

Optimal and Order-optimal Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Xi Chen , Yuze Chen , Ziyi Chen , Yuan Zhou This is my paper

Pith reviewed 2026-06-29 22:44 UTC · model grok-4.3

classification 💻 cs.LG math.OC
keywords online algorithmscompetitive analysisorder fulfillmentinventory managementgreedy policiestwo-layer networke-commerce logisticsadversarial model
0
0 comments X

The pith

Gated Priority-based Greedy policies attain competitive ratios that match or nearly match the best possible performance of any online algorithm for two-layer multi-item fulfillment under adversarial arrivals.

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

The paper develops a family of Gated Priority-based Greedy policies for deciding in real time whether to fulfill arriving multi-item orders from scarce local front distribution center inventory or to split them to a regional center when future demand is unknown. It proves these policies deliver competitive-ratio guarantees against an optimal clairvoyant planner that knows all arrivals in advance, under both time-varying and time-invariant item-specific costs that include fixed splitting penalties. The guarantees are shown to be tight or nearly tight by constructing matching or near-matching lower bounds that apply to every possible online algorithm. This establishes that simple, interpretable rules can achieve near-optimal worst-case performance without needing forecasts or complex optimization.

Core claim

A family of Gated Priority-based Greedy policies, which prioritize fulfillment locations and gate local inventory to protect it for potentially higher-value future orders, achieve competitive ratios under an adversarial online model with multiple front distribution centers, one regional center, multi-unit multi-item orders, and item-specific time-varying variable costs plus fixed splitting costs; these ratios are optimal or order-optimal because matching or near-matching lower bounds hold for any online algorithm.

What carries the argument

Gated Priority-based Greedy policies, which use priority ordering and inventory-protection gates to decide fulfillment locations and order splitting in real time.

If this is right

  • The policies perform strongly relative to generalized myopic and forecast-based benchmarks in numerical experiments.
  • Local inventory should be protected when future orders may have higher value, and splitting is worth the fixed-cost burden only under certain cost magnitudes.
  • The relative sizes of fixed and variable costs determine how much value more sophisticated optimization adds over the simple policies.
  • The same policies deliver guarantees under both time-varying and constant cost structures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If actual demand follows a stochastic process rather than an adversarial sequence, the same policies might achieve better average-case performance without changing the rules.
  • Adjusting the gate thresholds based on observed cost patterns could extend the approach to partially observable or slowly changing environments.
  • The priority and gating structure may apply to other sequential decision problems with fixed and variable costs, such as multi-location resource allocation.

Load-bearing premise

The analysis assumes an adversarial online arrival model with item-specific and time-varying variable costs plus fixed costs for splitting.

What would settle it

A specific sequence of order arrivals and cost realizations where any online policy, including the gated greedy ones, incurs a cost ratio strictly worse than the derived competitive ratio against the optimal offline solution.

read the original abstract

We study how an e-commerce firm should make real-time fulfillment decisions in a two-layer distribution network when multi-item customer orders arrive sequentially and future demand is unknown. The central managerial tension is whether to use scarce front distribution center (FDC) inventory to save current fulfillment cost or preserve that inventory for future orders that may be more valuable to serve locally. We formulate an adversarial online model with multiple FDCs, one regional distribution center (RDC), multi-unit multi-item orders, and item-specific and time-varying variable costs. Our theoretical objective is to characterize when simple, interpretable, and implementable fulfillment rules can perform nearly as well as an optimal clairvoyant planner. We develop a family of Gated Priority-based Greedy policies, derive competitive-ratio guarantees under both time-varying and time-invariant cost structures, and establish matching or near-matching lower bounds for any online algorithm. Numerical experiments show that the proposed policies perform strongly relative to generalized myopic and forecast-based benchmarks. The analysis yields managerial guidance on when local inventory should be protected, when splitting orders is worth the fixed-cost burden, and how the relative magnitudes of fixed and variable costs determine the value of more sophisticated optimization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper formulates an adversarial online model for real-time fulfillment decisions in a two-layer (FDC/RDC) distribution network with multi-item, multi-unit orders arriving sequentially under item-specific time-varying variable costs and fixed splitting costs. It introduces a family of Gated Priority-based Greedy policies, derives competitive-ratio guarantees for both time-varying and time-invariant cost structures, proves matching or near-matching lower bounds that apply to any online algorithm, and reports numerical experiments comparing the policies to myopic and forecast-based benchmarks.

Significance. If the competitive-ratio derivations and lower-bound constructions hold, the work supplies a clean theoretical characterization of when simple, interpretable policies achieve near-optimal performance in an explicitly adversarial online setting; the matching lower bounds and the explicit managerial guidance on inventory protection versus splitting are the primary contributions.

minor comments (3)
  1. [Abstract] The abstract states that matching or near-matching lower bounds are established, but the precise conditions distinguishing the two cases are not summarized; a one-sentence clarification would help readers locate the relevant theorems.
  2. [Numerical experiments] Numerical experiments section: the description of benchmark implementations and demand-generation parameters is brief; adding a short table or paragraph listing the exact parameter ranges used for the time-varying cost instances would improve reproducibility.
  3. [Policy definition] The policy definition introduces a gating threshold whose dependence on the cost structure is described qualitatively; an explicit formula or pseudocode line showing how the threshold is computed from the input parameters would remove ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the paper's contributions and the recommendation of minor revision. The report provides a clear summary and significance statement but does not enumerate any specific major comments requiring response.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper formulates an adversarial online model with item-specific time-varying costs and splitting fixed costs, then constructs Gated Priority-based Greedy policies and derives competitive ratios plus matching lower bounds directly from those definitions. No load-bearing step reduces to a fitted parameter renamed as prediction, a self-definitional construct, or a self-citation chain whose cited result itself depends on the target claim. The analysis remains self-contained against the stated model and policy rules, consistent with the reader's assessment of independent content.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the adversarial online model formulation and standard techniques from competitive analysis; no free parameters, invented entities, or ad-hoc axioms are mentioned in the abstract.

axioms (1)
  • domain assumption Adversarial online arrival model with unknown future demand and item-specific time-varying costs
    The model is explicitly formulated as adversarial online with these features.

pith-pipeline@v0.9.1-grok · 5747 in / 1204 out tokens · 28206 ms · 2026-06-29T22:44:28.540778+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 29 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]

    Manufacturing & Service Operations Management 17(1):34--51, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2014.0505

    Acimovic J, Graves SC (2015) Making Better Fulfillment Decisions on the Fly in an Online Retail Environment . Manufacturing & Service Operations Management 17(1):34--51, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2014.0505

    work page doi:10.1287/msom.2014.0505 2015

  4. [4]

    Manufacturing & Service Operations Management 19(3):419--436, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2016.0614

    Acimovic J, Graves SC (2017) Mitigating Spillover in Online Retailing via Replenishment . Manufacturing & Service Operations Management 19(3):419--436, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2016.0614

    work page doi:10.1287/msom.2016.0614 2017

  5. [5]

    Management Science ISSN 0025-1909, ://dx.doi.org/10.1287/mnsc.2023.00357

    Amil A, Makhdoumi A, Wei Y (2025) Multi- Item Order Fulfillment Revisited : LP Formulation and Prophet Inequality . Management Science ISSN 0025-1909, ://dx.doi.org/10.1287/mnsc.2023.00357

    work page doi:10.1287/mnsc.2023.00357 2025

  6. [6]

    INFORMS Journal on Applied Analytics 49(5):355--370, ISSN 2644-0865, 2644-0873, ://dx.doi.org/10.1287/inte.2019.1013

    Andrews JM, Farias VF, Khojandi AI, Yan CM (2019) Primal-- Dual Algorithms for Order Fulfillment at Urban Outfitters , Inc . INFORMS Journal on Applied Analytics 49(5):355--370, ISSN 2644-0865, 2644-0873, ://dx.doi.org/10.1287/inte.2019.1013

    work page doi:10.1287/inte.2019.1013 2019

  7. [7]

    Operations Research 57(4):950--963, ISSN 0030-364X, 1526-5463, ://dx.doi.org/10.1287/opre.1080.0654

    Ball MO, Queyranne M (2009) Toward Robust Revenue Management : Competitive Analysis of Online Booking . Operations Research 57(4):950--963, ISSN 0030-364X, 1526-5463, ://dx.doi.org/10.1287/opre.1080.0654

    work page doi:10.1287/opre.1080.0654 2009

  8. [8]

    Foundations and Trends in Theoretical Computer Science 3(2--3):93--263, ://dx.doi.org/10.1561/0400000024

    Buchbinder N, Naor J (2009) The Design of Competitive Online Algorithms via a Primal-Dual Approach . Foundations and Trends in Theoretical Computer Science 3(2--3):93--263, ://dx.doi.org/10.1561/0400000024

    work page doi:10.1561/0400000024 2009

  9. [9]

    Management Science 66(7):2993--3009, ISSN 0025-1909, 1526-5501, ://dx.doi.org/10.1287/mnsc.2019.3365

    Bumpensanti P, Wang H (2020) A Re-Solving Heuristic with Uniformly Bounded Loss for Network Revenue Management . Management Science 66(7):2993--3009, ISSN 0025-1909, 1526-5501, ://dx.doi.org/10.1287/mnsc.2019.3365

    work page doi:10.1287/mnsc.2019.3365 2020

  10. [10]

    European Journal of Operational Research 311(3):1009--1022, ISSN 0377-2217, ://dx.doi.org/10.1016/j.ejor.2023.06.018

    Goedhart J, Haijema R, Akkerman R, de Leeuw S (2023) Replenishment and fulfilment decisions for stores in an omni-channel retail network. European Journal of Operational Research 311(3):1009--1022, ISSN 0377-2217, ://dx.doi.org/10.1016/j.ejor.2023.06.018

    work page doi:10.1016/j.ejor.2023.06.018 2023

  11. [11]

    Naval Research Logistics (NRL) 68(6):779--794, ISSN 0894-069X, 1520-6750, ://dx.doi.org/10.1002/nav.21969

    Govindarajan A, Sinha A, Uichanco J (2021) Joint inventory and fulfillment decisions for omnichannel retail networks. Naval Research Logistics (NRL) 68(6):779--794, ISSN 0894-069X, 1520-6750, ://dx.doi.org/10.1002/nav.21969

    work page doi:10.1002/nav.21969 2021

  12. [12]

    Operations Research 73(4):1897--1915, ISSN 0030-364X, 1526-5463, ://dx.doi.org/10.1287/opre.2021.0695

    Goyal V, Iyengar G, Udwani R (2025) Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources . Operations Research 73(4):1897--1915, ISSN 0030-364X, 1526-5463, ://dx.doi.org/10.1287/opre.2021.0695

    work page doi:10.1287/opre.2021.0695 2025

  13. [13]

    Manufacturing & Service Operations Management 21(1):47--65, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2018.0737

    Harsha P, Subramanian S, Uichanco J (2019) Dynamic Pricing of Omnichannel Inventories . Manufacturing & Service Operations Management 21(1):47--65, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2018.0737

    work page doi:10.1287/msom.2018.0737 2019

  14. [14]

    ://dx.doi.org/10.2139/ssrn.5133857

    He S, Wei Y, Xu J, Yu SH (2025) Online Resource Allocation without Re-solving : The Effectiveness of Primal-Dual Policies . ://dx.doi.org/10.2139/ssrn.5133857

    work page doi:10.2139/ssrn.5133857 2025

  15. [15]

    European Journal of Operational Research 302(3):799--818, ISSN 03772217, ://dx.doi.org/10.1016/j.ejor.2021.12.021

    H \"u bner A, Hense J, Dethlefs C (2022) The revival of retail stores via omnichannel operations: A literature review and research framework. European Journal of Operational Research 302(3):799--818, ISSN 03772217, ://dx.doi.org/10.1016/j.ejor.2021.12.021

    work page doi:10.1016/j.ejor.2021.12.021 2022

  16. [16]

    Mathematics of Operations Research 37(2):313--345, ISSN 0364-765X, 1526-5471, ://dx.doi.org/10.1287/moor.1120.0537

    Jasin S, Kumar S (2012) A Re-Solving Heuristic with Bounded Revenue Loss for Network Revenue Management with Customer Choice . Mathematics of Operations Research 37(2):313--345, ISSN 0364-765X, 1526-5471, ://dx.doi.org/10.1287/moor.1120.0537

    work page doi:10.1287/moor.1120.0537 2012

  17. [17]

    ://dx.doi.org/10.13140/RG.2.1.2970.5680

    Jasin S, Sinha A (2015) An LP-Based Correlated Rounding Scheme for Multi-Item Ecommerce Order Fulfillment . ://dx.doi.org/10.13140/RG.2.1.2970.5680

    work page doi:10.13140/rg.2.1.2970.5680 2015

  18. [18]

    Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing - STOC '90 , 352--358 (Baltimore, Maryland, United States: ACM Press), ISBN 978-0-89791-361-4, ://dx.doi.org/10.1145/100216.100262

    work page doi:10.1145/100216.100262 1990

  19. [19]

    Management Science 54(9):1594--1609, ISSN 0025-1909, 1526-5501, ://dx.doi.org/10.1287/mnsc.1080.0859

    Lan Y, Gao H, Ball MO, Karaesmen I (2008) Revenue Management with Limited Demand Information . Management Science 54(9):1594--1609, ISSN 0025-1909, 1526-5501, ://dx.doi.org/10.1287/mnsc.1080.0859

    work page doi:10.1287/mnsc.1080.0859 2008

  20. [20]

    Manufacturing & Service Operations Management 20(2):269--284, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2017.0641

    Lei YM, Jasin S, Sinha A (2018) Joint Dynamic Pricing and Order Fulfillment for E-commerce Retailers . Manufacturing & Service Operations Management 20(2):269--284, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2017.0641

    work page doi:10.1287/msom.2017.0641 2018

  21. [21]

    ://dx.doi.org/10.48550/arXiv.2603.04065

    Ling Z, Jiang J, Xin L (2026) Online Order Fulfillment with Replenishment . ://dx.doi.org/10.48550/arXiv.2603.04065

    work page doi:10.48550/arxiv.2603.04065 2026

  22. [22]

    Manufacturing & Service Operations Management 25(4):1324--1337, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2023.1219

    Ma W (2023) Order- Optimal Correlated Rounding for Fulfilling Multi-Item E-Commerce Orders . Manufacturing & Service Operations Management 25(4):1324--1337, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2023.1219

    work page doi:10.1287/msom.2023.1219 2023

  23. [23]

    Vazirani and Vijay V

    Mehta A, Saberi A, Vazirani U, Vazirani V (2007) AdWords and generalized online matching. Journal of the ACM 54(5):22, ISSN 0004-5411, 1557-735X, ://dx.doi.org/10.1145/1284320.1284321

    work page doi:10.1145/1284320.1284321 2007

  24. [24]

    Computers & Industrial Engineering 160:107546, ISSN 0360-8352, ://dx.doi.org/10.1016/j.cie.2021.107546

    Qiu R, Hou L, Sun Y, Sun M, Sun Y (2021) Joint pricing, ordering and order fulfillment decisions for a dual-channel supply chain with demand uncertainties: A distribution-free approach. Computers & Industrial Engineering 160:107546, ISSN 0360-8352, ://dx.doi.org/10.1016/j.cie.2021.107546

    work page doi:10.1016/j.cie.2021.107546 2021

  25. [25]

    Manufacturing & Service Operations Management (M&SOM) (INFORMS) 26(1):2--10, ISSN 1523-4614, ://dx.doi.org/10.1287/msom.2020.0900

    Shen M, Tang CS, Wu D, Yuan R, Zhou W (2024) JD .com: Transaction-Level Data for the 2020 MSOM Data Driven Research Challenge . Manufacturing & Service Operations Management (M&SOM) (INFORMS) 26(1):2--10, ISSN 1523-4614, ://dx.doi.org/10.1287/msom.2020.0900

    work page doi:10.1287/msom.2020.0900 2024

  26. [26]

    Management Science 71(10):8908--8926, ISSN 0025-1909, 1526-5501, ://dx.doi.org/10.1287/mnsc.2023.02588

    Simchi-Levi D, Zheng Z, Zhu F (2025) On Greedy-Like Policies in Online Matching with Reusable Network Resources and Decaying Rewards . Management Science 71(10):8908--8926, ISSN 0025-1909, 1526-5501, ://dx.doi.org/10.1287/mnsc.2023.02588

    work page doi:10.1287/mnsc.2023.02588 2025

  27. [27]

    Manufacturing & Service Operations Management 23(6):1634--1650, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2020.0903

    Wei L, Kapuscinski R, Jasin S (2021) Shipping Consolidation Across Two Warehouses with Delivery Deadline and Expedited Options for E-commerce and Omni-channel Retailers . Manufacturing & Service Operations Management 23(6):1634--1650, ISSN 1523-4614, 1526-5498, ://dx.doi.org/10.1287/msom.2020.0903

    work page doi:10.1287/msom.2020.0903 2021

  28. [28]

    Management Science mnsc.2023.00549, ISSN 0025-1909, 1526-5501, ://dx.doi.org/10.1287/mnsc.2023.00549

    Xie Y, Ma W, Xin L (2025) The Benefits of Delay to Online Decision Making . Management Science mnsc.2023.00549, ISSN 0025-1909, 1526-5501, ://dx.doi.org/10.1287/mnsc.2023.00549

    work page doi:10.1287/mnsc.2023.00549 2025

  29. [29]

    Manufacturing & Service Operations Management 11:340--355, ://dx.doi.org/10.1287/msom.1080.0222

    Xu P, Allgor R, Graves S (2009) Benefits of Reevaluating Real-Time Order Fulfillment Decisions . Manufacturing & Service Operations Management 11:340--355, ://dx.doi.org/10.1287/msom.1080.0222

    work page doi:10.1287/msom.1080.0222 2009

  30. [30]

    Operations Research 73(5):2297--2305, ISSN 0030-364X, 1526-5463, ://dx.doi.org/10.1287/opre.2022.0100

    Zhao Y, Wang X, Xin L (2025) Multi-item Online Order Fulfillment in a Two-Layer Network . Operations Research 73(5):2297--2305, ISSN 0030-364X, 1526-5463, ://dx.doi.org/10.1287/opre.2022.0100

    work page doi:10.1287/opre.2022.0100 2025

  31. [31]

    Operations Research 73(6):2914--2932, ://dx.doi.org/10.1287/opre.2023.0453

    Zhou Q, Gumus M, Miao S (2025) E-commerce Order Fulfillment Problem with Limited Time Window . Operations Research 73(6):2914--2932, ://dx.doi.org/10.1287/opre.2023.0453

    work page doi:10.1287/opre.2023.0453 2025