Average Distance of Random Bipartite Matching in One-Dimensional Spaces and Networks

References

• Abeywickrama T , Liang V , Tan KL (2022) Bipartite matching: What to do in the real world when computing assignment costs dominates finding the optimal assignment. SIGMOD Rec. 51(1):51–58.Crossref, Google Scholar
• Addario-Berry L , Reed BA (2008) Ballot theorems, old and new. Győri E , Katona GOH , Lovász L , Sági G , eds. Horizons of Combinatorics (Springer Berlin Heidelberg, Berlin, Heidelberg), 9–35.Crossref, Google Scholar
• 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
• Aloqaily M , Bouachir O , Al Ridhawi I , Tzes A (2022) An adaptive UAV positioning model for sustainable smart transportation. Sustainable Cities Soc. 78:103617.Crossref, Google Scholar
• Boeing G (2020) A multi-scale analysis of 27,000 urban street networks: Every US city, town, urbanized area, and Zillow neighborhood. Environ. Planning B Urban Anal. City Sci. 47(4):590–608.Crossref, Google Scholar
• Boniolo E , Caracciolo S , Sportiello A (2014) Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle. J. Statist. Mech. Theory Experiment 2014(11):P11023.Crossref, Google Scholar
• Caracciolo S , Sicuro G (2014) One-dimensional Euclidean matching problem: Exact solutions, correlation functions, and universality. Phys. Rev. E 90(4):042112.Crossref, Google Scholar
• Caracciolo S , Sicuro G (2015) Scaling hypothesis for the Euclidean bipartite matching problem. II. correlation functions. Phys. Rev. E 91(6):062125.Crossref, Google Scholar
• Caracciolo S , D’Achille M , Sicuro G (2017) Random Euclidean matching problems in one dimension. Phys. Rev. E 96(4):042102.Crossref, Google Scholar
• Caracciolo S , Di Gioacchino A , Malatesta EM , Molinari LG (2019) Selberg integrals in 1D random Euclidean optimization problems. J. Statist. Mech. Theory Experiment 2019(6):063401.Crossref, Google Scholar
• Caracciolo S , Lucibello C , Parisi G , Sicuro G (2014) Scaling hypothesis for the Euclidean bipartite matching problem. Phys. Rev. E 90(1):012118.Crossref, Google Scholar
• Crouse DF (2016) On implementing 2D rectangular assignment algorithms. IEEE Trans. Aerospace Electronic Systems 52(4):1679–1696.Crossref, Google Scholar
• Daganzo CF (1978) An approximate analytic model of many-to-many demand responsive transportation systems. Transportation Res. 12(5):325–333.Crossref, Google Scholar
• Daganzo CF , Smilowitz KR (2004) Bounds and approximations for the transportation problem of linear programming and other scalable network problems. Transportation Sci. 38(3):343–356.Link, Google Scholar
• Ding Y , McCormick ST , Nagarajan M (2021) A fluid model for one-sided bipartite matching queues with match-dependent rewards. Oper. Res. 69(4):1256–1281.Link, Google Scholar
• Duan Y , Lu F (2014) Robustness of city road networks at different granularities. Physica A Statist. Mech. Appl. 411:21–34.Crossref, Google Scholar
• Dutta A , Dasgupta P (2017) Bipartite graph matching-based coordination mechanism for multi-robot path planning under communication constraints. 2017 IEEE Internat. Conf. Robotics Automation ICRA (IEEE, Piscataway, NJ), 857–862.Google Scholar
• Ellis D (2011) The expansion of random regular graphs. https://snap.stanford.edu/class/cs224w-readings/ellis11expansion.pdf.Google Scholar
• Ezaki T , Fujitsuka K , Imura N , Nishinari K (2024) Drone-based vertical delivery system for high-rise buildings: Multiple drones vs. a single elevator. Comm. Transportation Res. 4:100130.Crossref, Google Scholar
• Fedtke S , Boysen N (2017) A comparison of different container sorting systems in modern rail-rail transshipment yards. Transportation Res. Part C Emerging Tech. 82:63–87.Crossref, Google Scholar
• Georgiev D , Liò P (2020) Neural bipartite matching. Preprint, submitted May 22, https://arxiv.org/abs/2005.11304v1.Google Scholar
• Ghassemi P , Chowdhury S (2018) Decentralized task allocation in multi-robot systems via bipartite graph matching augmented with fuzzy clustering. 44th Design Automation Conf. Internat. Design Engrg. Tech. Conf. Comput. Inform. Engrg. Conf. , vol. 2A (American Society of Mechanical Engineers, New York), V02AT03A014.Google Scholar
• Goldberg AV (1997) An efficient implementation of a scaling minimum-cost flow algorithm. J. Algorithms 22(1):1–29.Crossref, Google Scholar
• Harel A (1993) Random walk and the area below its path. Math. Oper. Res. 18(3):566–577.Link, Google Scholar
• Hernández D , Cecília JM , Calafate CT , Cano JC , Manzoni P (2021) The Kuhn-Munkres algorithm for efficient vertical takeoff of UAV swarms. 2021 IEEE 93rd Vehicular Tech. Conf. VTC2021-Spring (IEEE, Piscataway, NJ), 1–5.Google Scholar
• Jin C , Xu J , Han Y , Hu J , Chen Y , Huang J (2022) Efficient delay-aware task scheduling for IoT devices in mobile cloud computing. Mobile Inform. Systems 2022(1):1849877.Google Scholar
• Jonker R , Volgenant A (1987) A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38(4):325–340.Crossref, Google Scholar
• Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2:83–97.Crossref, Google Scholar
• Lanczos C (1964) A precision approximation of the gamma function. J. Soc. Indust. Appl. Math. Ser. B Numer. Anal. 1(1):86–96.Crossref, Google Scholar
• Mézard M , Parisi G (1985) Replicas and optimization. J. Phys. Lett. 46(17):771–778.Google Scholar
• Mézard M , Parisi G (1988) The Euclidean matching problem. J. Phys. 49(12):2019–2025.Crossref, Google Scholar
• Ouyang Y , Yang H (2023) Measurement and mitigation of the “wild goose chase” phenomenon in taxi services. Transportation Res. Part B Methodological 167:217–234.Crossref, Google Scholar
• Panigrahy NK , Basu P , Nain P , Towsley D , Swami A , Chan KS , Leung KK (2020) Resource allocation in one-dimensional distributed service networks with applications. Performance Eval. 142:102110.Crossref, Google Scholar
• Seth A , James A , Kuantama E , Mukhopadhyay S , Han R (2023) Drone high-rise aerial delivery with vertical grid screening. Drones 7(5):300.Crossref, Google Scholar
• Shen S , Ouyang Y (2023) Dynamic and Pareto-improving swapping of vehicles to enhance integrated and modular mobility services. Transportation Res. Part C Emerging Tech. 157:104366.Crossref, Google Scholar
• Shen S , Zhai Y , Ouyang Y (2024) Expected bipartite matching distance in a d-dimensional l p space: Approximate closed-form formulas and applications to mobility services. Preprint, submitted June 18, https://arxiv.org/abs/2406.12174v1.Google Scholar
• Stiglic M , Agatz N , Savelsbergh M , Gradisar M (2015) The benefits of meeting points in ride-sharing systems. Transportation Res. Part B Methodological 82:36–53.Crossref, Google Scholar
• Tafreshian A , Masoud N (2020) Trip-based graph partitioning in dynamic ridesharing. Transportation Res. Part C Emerging Tech. 114:532–553.Crossref, Google Scholar
• Wang M , Chen Z , Mu L , Zhang X (2020) Road network structure and ride-sharing accessibility: A network science perspective. Comput. Environ. Urban Systems 80:101430.Crossref, Google Scholar
• Wang X , He F , Yang H , Oliver Gao H (2016) Pricing strategies for a taxi-hailing platform. Transportation Res. Part E Logist. Transportation Rev. 93:212–231.Crossref, Google Scholar
• Wang Y , Makedon F , Ford J , Huang H (2004) A bipartite graph matching framework for finding correspondences between structural elements in two proteins. 26th Annu. Internat. Conf. IEEE Engrg, Medicine Biology Soc. , vol. 2 (IEEE, Piscataway, NJ), 2972–2975.Google Scholar
• Werman M , Peleg S , Melter R , Kong T (1986) Bipartite graph matching for points on a line or a circle. J. Algorithms 7(2):277–284.Crossref, Google Scholar
• Yang H , Leung C , Wong S , Bell M (2010) Equilibria of bilateral taxi–customer searching and meeting on networks. Transportation Res. Part B Methodological 44:1067–1083.Crossref, Google Scholar
• Zhang Y , Phillips CA , Rogers GL , Baker EJ , Chesler EJ , Langston MA (2014) On finding bicliques in bipartite graphs: A novel algorithm and its application to the integration of diverse biological data types. BMC Bioinformatics 15(1):110.Crossref, Google Scholar
• Zhou Y , Yang H , Ke J (2022) Price of competition and fragmentation in ride-sourcing markets. Transportation Res. Part C Emerging Tech. 143:103851.Crossref, Google Scholar