Multi-Item Order Fulfillment Revisited: LP Formulation and Prophet Inequality

References

• Acimovic J, Farias VF (2019) The fulfillment-optimization problem. INFORMS TutORials Oper. Res. 218–237.Google Scholar
• Acimovic J, Graves SC (2015) Making better fulfillment decisions on the fly in an online retail environment. Manufacturing Service Oper. Management 17(1):34–51.Link, Google Scholar
• Acimovic J, Graves SC (2017) Mitigating spillover in online retailing via replenishment. Manufacturing Service Oper. Management 19(3):419–436.Link, Google Scholar
• Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• Andrews JM, Farias VF, Khojandi AI, Yan CM (2019) Primal–dual algorithms for order fulfillment at Urban Outfitters, Inc. INFORMS J. Appl. Anal. 49(5):355–370.Link, Google Scholar
• Aouad A, Saban D (2023) Online assortment optimization for two-sided matching platforms. Management Sci. 69(4):2069–2087.Google Scholar
• Aouad A, Saritaç Ö (2020) Dynamic stochastic matching under limited time. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 789–790.Google Scholar
• Asadpour A, Wang X, Zhang J (2020) Online resource allocation with limited flexibility. Management Sci. 66(2):642–666.Link, Google Scholar
• Ashlagi I, Burq M, Jaillet P, Manshadi V (2019a) On matching and thickness in heterogeneous dynamic markets. Oper. Res. 67(4):927–949.Abstract, Google Scholar
• Ashlagi I, Burq M, Dutta C, Jaillet P, Saberi A, Sholley C (2019b) Edge weighted online windowed matching. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 729–742.Google Scholar
• Azar PD, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1358–1377.Google Scholar
• Babaioff M, Immorlica N, Kleinberg R (2007) Matroids, secretary problems, and online mechanisms. Proc. 18th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 434–443.Google Scholar
• Baek J, Ma W (2022) Technical note—Bifurcating constraints to improve approximation ratios for network revenue management with reusable resources. Oper. Res. 70(4):2226–2236.Link, Google Scholar
• Balseiro SR, Brown DB (2019) Approximations to stochastic dynamic programs via information relaxation duality. Oper. Res. 67(2):577–597.Abstract, Google Scholar
• Castro F, Nazerzadeh H, Yan C (2020) Matching queues with reneging: A product form solution. Queueing Systems 96:359–385.Crossref, Google Scholar
• Chen X, Feldman J, Jung SH, Kouvelis P (2022) Approximation schemes for the joint inventory selection and online resource allocation problem. Production Oper. Management 31(8):3143–3159.Crossref, Google Scholar
• Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2019) Recent developments in prophet inequalities. ACM SIGecom Exchanges 17(1):61–70.Crossref, Google Scholar
• Désir A, Goyal V, Zhang J (2022) Capacitated assortment optimization: Hardness and approximation. Oper. Res. 70(2):893–904.Link, Google Scholar
• DeValve L, Wei Y, Wu D, Yuan R (2023) Understanding the value of fulfillment flexibility in an online retailing environment. Manufacturing Service Oper. Management 25(2):391–408.Link, Google Scholar
• Dutting P, Feldman M, Kesselheim T, Lucier B (2020) Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM J. Comput. 49(3):540–582.Crossref, Google Scholar
• Elmachtoub AN, Levi R (2016) Supply chain management with online customer selection. Oper. Res. 64(2):458–473.Link, Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1−1/e. 2009 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 117–126.Google Scholar
• Feng Y, Niazadeh R (2024) Batching and optimal multi-stage bipartite allocations. Management Sci., ePub ahead of print August 30, https://doi.org/10.1287/mnsc.2022.03698.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2022) Near-optimal Bayesian online assortment of reusable resources. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 964–965.Google Scholar
• Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
• Harsha P, Subramanian S, Uichanco J (2019) Dynamic pricing of omnichannel inventories. Manufacturing Service Oper. Management 21(1):47–65.Link, Google Scholar
• Jasin S, Sinha A (2015) An LP-based correlated rounding scheme for multi-item ecommerce order fulfillment. Oper. Res. 63(6):1336–1351.Link, Google Scholar
• Jiang J, Ma W, Zhang J (2024) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Oper. Res., ePub ahead of print June 3, https://doi.org/10.1287/opre.2022.0309.Google Scholar
• Johari R, Kamble V, Kanoria Y (2021) Matching while learning. Oper. Res. 69(2):655–681.Link, Google Scholar
• Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. 44th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 123–136.Google Scholar
• Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Probab. Banach Spaces 4:197–266.Google Scholar
• Lei YM, Jasin S, Sinha A (2018) Joint dynamic pricing and order fulfillment for e-commerce retailers. Manufacturing Service Oper. Management 20(2):269–284.Link, Google Scholar
• Lo I, Manshadi V, Rodilitz S, Shameli A (2024) Commitment on volunteer crowdsourcing platforms: Implications for growth and engagement. Manufacturing Service Oper. Management 26(5):1787–1805.Google Scholar
• Ma W (2023) Order-optimal correlated rounding for fulfilling multi-item e-commerce orders. Manufacturing Service Oper. Management 25(4):1324–1337.Link, Google Scholar
• Ma W, Simchi-Levi D (2020) Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios. Oper. Res. 68(6):1787–1803.Link, Google Scholar
• Ma W, Simchi-Levi D, Teo C-P (2021) On policies for single-leg revenue management with limited demand information. Oper. Res. 69(1):207–226.Link, Google Scholar
• 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.Link, Google Scholar
• Manshadi V, Rodilitz S (2020) Online policies for efficient volunteer crowdsourcing. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 315–316.Google Scholar
• Manshadi VH, Gharan SO, Saberi A (2012) Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res. 37(4):559–573.Link, Google Scholar
• Manshadi V, Rodilitz S, Saban D, Suresh A (2024) Online algorithms for matching platforms with multi-channel traffic. Management Sci., ePub ahead of print December 30, https://doi.org/10.1287/mnsc.2022.00910.Google Scholar
• Mehta A (2013) Online Matching and Ad Allocation, Foundations and Trends in Theoretical Computer Science, vol. 8, no. 4 (Now Publishers, Inc., Hanover, MA), 265–368.Google Scholar
• Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213–1216.Crossref, Google Scholar
• Statista Research Department (2023) Retail e-commerce sales worldwide from 2014 to 2027. Accessed June 1, 2024, https://www.statista.com/statistics/379046/worldwide-retail-e-commerce-sales/.Google Scholar
• Statista Research Department (2024) Revenue of the e-commerce industry in the U.S. 2018–2028. Accessed September 1, 2024, https://www.statista.com/statistics/272391/us-retail-e-commerce-sales-forecast/\#statisticContainer.Google Scholar
• Truong V-A, Wang X (2019) Prophet inequality with correlated arrival probabilities, with application to two sided matchings. Preprint, submitted January 8, https://arxiv.org/abs/1901.02552.Google Scholar
• Xu PJ, Allgor R, Graves SC (2009) Benefits of reevaluating real-time order fulfillment decisions. Manufacturing Service Oper. Management 11(2):340–355.Link, Google Scholar
• Xu Z, Zhang H, Zhang J, Zhang RQ (2020) Online demand fulfillment under limited flexibility. Management Sci. 66(10):4667–4685.Link, Google Scholar
• Zhao Y, Wang X, Xin L (2022) Multi-item online order fulfillment in a two-layer network. Preprint, submitted October 1, 2020, http://dx.doi.org/10.2139/ssrn.3675117.Google Scholar