Designing Sparse Graphs for Stochastic Matching with an Application to Middle-Mile Transportation Management

References

• Afèche P, Caldentey R, Gupta V (2022) On the optimal design of a bipartite matching queueing system. Oper. Res. 70(1):363–401.Link, Google Scholar
• Allon G, Van Mieghem JA (2010) Global dual sourcing: Tailored base-surge allocation to near-and offshore production. Management Sci. 56(1):110–124.Link, Google Scholar
• Angluin D, Valiant L (1979) Fast probabilistic algorithms for Hamiltonian paths and matchings. J. Comput. System Sci. 18(2):155–193.Crossref, Google Scholar
• Aronson J, Frieze A, Pittel BG (1998) Maximum matchings in sparse random graphs: Karp–Sipser revisited. Random Structures Algorithms 12(2):111–177.Crossref, 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, Gamarnik D, Rees MA, Roth AE (2012) The need for (long) chains in kidney exchange. Working Paper No. 18202, National Bureau of Economic Research, Cambridge, MA.Google Scholar
• Assadi S, Bernstein A (2019) Toward a unified theory of sparsification for matching problems. Proc. Second Sympos. Simplicity Algorithms (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany), 11:1–11:20.Google Scholar
• Assadi S, Khanna S, Li Y (2016) The stochastic matching problem with (very) few queries. Proc. 2016 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 43–60.Google Scholar
• Bassamboo A, Randhawa RS, Van Mieghem JA (2010) Optimal flexibility configurations in newsvendor networks: Going beyond chaining and pairing. Management Sci. 56(8):1285–1303.Link, Google Scholar
• Bassamboo A, Randhawa RS, Van Mieghem JA (2012) A little flexibility is all you need: On the asymptotic value of flexible capacity in parallel queuing systems. Oper. Res. 60(6):1423–1435.Link, Google Scholar
• Behnezhad S, Derakhshan M, Hajiaghayi MT (2020) Stochastic matching with few queries: (1-ϵ) approximation. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1111–1124.Google Scholar
• Behnezhad S, Farhadi A, Hajiaghayi MT, Reyhani N (2019a) Stochastic matching with few queries: New algorithms and tools. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2855–2874.Google Scholar
• Behnezhad S, Derakhshan M, Farhadi A, Hajiaghayi M, Reyhani N (2019b) Stochastic matching on uniformly sparse graphs. Fotakis D, Markakis E, eds. Algorithmic Game Theory (Springer, Cham, Switzerland), 357–373.Google Scholar
• Berge C (1958) Sur le couplage maximum d’un graphe. Comptes Rendus de l’Académie des Sciences 247(3):258–259.Google Scholar
• Blum N (1990) A new approach to maximum matching in general graphs. Paterson MS, ed. Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 443 (Springer, Berlin), 586–597.Google Scholar
• Blum A, Dickerson JP, Haghtalab N, Procaccia AD, Sandholm T, Sharma A (2020) Ignorance is almost bliss: Near-optimal stochastic matching with few queries. Oper. Res. 68(1):16–34.Link, Google Scholar
• Bollobás B, Béla B (2001) Random Graphs, 2nd ed. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Chebolu P, Frieze A, Melsted P (2010) Finding a maximum matching in a sparse random graph in o(n) expected time. J. ACM 57(4):1–27.Crossref, Google Scholar
• Chen S, Song JS, Wei Y (2020) Data-driven scalable e-commerce transportation network design with unknown flow response. Preprint, submitted May 29, https://dx.doi.org/10.2139/ssrn.3590865.Google Scholar
• Chen X, Zhang J, Zhou Y (2015) Optimal sparse designs for process flexibility via probabilistic expanders. Oper. Res. 63(5):1159–1176.Link, Google Scholar
• Chou MC, Teo CP, Zheng H (2008) Process flexibility: Design, evaluation, and applications. Flexible Services Manufacturing J. 20(1–2):59–94.Crossref, Google Scholar
• Deng T, Shen ZJM (2013) Process flexibility design in unbalanced networks. Manufacturing Service Oper. Management 15(1):24–32.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
• Dickerson JP, Procaccia AD, Sandholm T (2012) Optimizing kidney exchange with transplant chains: Theory and reality. Proc. 11th Internat. Conf. Autonomous Agents Multiagent Systems, vol. 2 (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 711–718.Google Scholar
• Ding Y, Ge D, He S, Ryan CT (2018) A nonasymptotic approach to analyzing kidney exchange graphs. Oper. Res. 66(4):918–935.Link, Google Scholar
• Edmonds J (1965) Paths, trees and flowers. Canadian J. Math. 17:449–467.Crossref, Google Scholar
• Erdős P, Rényi A (1966) On the existence of a factor of degree one of a connected random graph. Acta Math. Academiae Scientiarum Hungarica 17(3–4):359–368.Crossref, Google Scholar
• Even S, Kariv O (1975) An O(n2.5) algorithm for maximum matching in general graphs. Proc. IEEE 16th Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 100–112.Google Scholar
• Frieze AM (1986) On large matchings and cycles in sparse random graphs. Discrete Math. 59(3):243–256.Crossref, Google Scholar
• Frieze A, Karoński M (2016) Introduction to Random Graphs (Cambridge University Press, Cambridge, UK).Google Scholar
• Fujii M, Kasami T, Ninomiya K (1969) Optimal sequencing of two equivalent processors. SIAM J. Appl. Math. 17(4):784–789.Crossref, Google Scholar
• Galil Z (1986) Efficient algorithms for finding maximum matching in graphs. ACM Comput. Surveys 18(1):23–38.Crossref, Google Scholar
• Graves SC, Tomlin BT (2003) Process flexibility in supply chains. Management Sci. 49(7):907–919.Link, Google Scholar
• Hall P (1935) On representatives of subsets. J. London Math. Soc. s1-10(1):26–30.Crossref, Google Scholar
• Hopcroft J, Karp R (1973) An O(n2.5) algorithm for maximum matching in bipartite graphs. SIAM J. Comput. 2(4):225–231.Crossref, Google Scholar
• Hull JC (2018) Risk Management and Financial Institutions, 5th ed. (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Iravani SMR, Kolfal B, Van Oyen MP (2007) Call-center labor cross-training: Its a small world after all. Management Sci. 53(7):1102–1112.Link, Google Scholar
• Jordan WC, Graves SC (1995) Principles on the benefits of manufacturing process flexibility. Management Sci. 41(4):577–594.Link, Google Scholar
• Kameda T, Munro I (1974) An O(|V||E|) algorithm for maximum matching of graphs. Computing 12:91–98.Crossref, Google Scholar
• Karp RM, Sipser M (1981) Maximum matching in sparse random graphs. Proc. IEEE 22nd Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 364–375.Google Scholar
• Ledvina K, Qin H, Simchi-Levi D, Wei Y (2022) A new approach for vehicle routing with stochastic demand: Combining route assignment with process flexibility. Oper. Res. 70(5):2655–2673.Link, Google Scholar
• Lyu G, Cheung WC, Chou MC, Teo CP, Zheng Z, Zhong Y (2019) Capacity allocation in flexible production networks: Theory and applications. Management Sci. 65(11):5091–5109.Link, Google Scholar
• May JW (2015) Cheminformatics for genome-scale metabolic reconstructions. Unpublished PhD thesis, University of Cambridge, Cambridge, UK.Google Scholar
• Micali S, Vazirani V (1980) An O(VE) algorithm for finding maximum matching in general graphs. Proc. 21st IEEE Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society Press, Los Alamitos, CA), 17–27.Google Scholar
• Naughton K, Boyle M (2019) Walmart targets automated “middle-mile” delivery to cut shipping costs. Transport Topics (June 19), https://www.ttnews.com/articles/walmart-targets-automated-middle-mile-delivery-cut-shipping-costs.Google Scholar
• Qin H, Xiao J, Ge D, Xin L, Gao J, He S, Hu H, Carlsson JG (2022) JD.com: Operations research algorithms drive intelligent warehouse robots to work. INFORMS J. Appl. Anal. 52(1):42–55.Link, Google Scholar
• Roth AE, Sönmez T, Ünver MU (2005) Pairwise kidney exchange. J. Econom. Theory 125(2):151–188.Crossref, Google Scholar
• Shi C, Wei Y, Zhong Y (2019) Process flexibility for multi-period production systems. Oper. Res. 67(5):1300–1320.Link, Google Scholar
• Simchi-Levi D, Wei Y (2012) Understanding the performance of the long chain and sparse designs in process flexibility. Oper. Res. 60(5):1125–1141.Link, Google Scholar
• Tsitsiklis JN, Xu K (2017) Flexible queueing architectures. Oper. Res. 65(5):1398–1413.Link, Google Scholar
• Tutte WT (1947) The factorization of linear graphs. J. London Math. Soc. 1(2):107–111.Crossref, Google Scholar
• Wang X, Zhang J (2015) Process flexibility: A distribution-free bound on the performance of k-chain. Oper. Res. 63(3):555–571.Link, Google Scholar
• Wolsey LA (1998) Integer Programming (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Xin L, Goldberg DA (2018) Asymptotic optimality of tailored base-surge policies in dual-sourcing inventory systems. Management Sci. 64(1):437–452.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