{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T00:39:12Z","timestamp":1712363952245},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T00:00:00Z","timestamp":1701302400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the minimum spanning tree problem on a weighted complete bipartite graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000445_inline1.png\" \/><jats:tex-math>\n$K_{n_R, n_B}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> whose <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000445_inline2.png\" \/><jats:tex-math>\n$n=n_R+n_B$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices are random, i.i.d. uniformly distributed points in the unit cube in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000445_inline3.png\" \/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> dimensions and edge weights are the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000445_inline4.png\" \/><jats:tex-math>\n$p$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-th power of their Euclidean distance, with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000445_inline5.png\" \/><jats:tex-math>\n$p\\gt 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. In the large <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000445_inline6.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> limit with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000445_inline7.png\" \/><jats:tex-math>\n$n_R\/n \\to \\alpha _R$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000445_inline8.png\" \/><jats:tex-math>\n$0\\lt \\alpha _R\\lt 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, we show that the maximum vertex degree of the tree grows logarithmically, in contrast with the classical, non-bipartite, case, where a uniform bound holds depending on <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000445_inline9.png\" \/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> only. Despite this difference, for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000445_inline10.png\" \/><jats:tex-math>\n$p\\lt d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, we are able to prove that the total edge costs normalized by the rate <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000445_inline11.png\" \/><jats:tex-math>\n$n^{1-p\/d}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> converge to a limiting constant that can be represented as a series of integrals, thus extending a classical result of Avram and Bertsimas to the bipartite case and confirming a conjecture of Riva, Caracciolo and Malatesta.<\/jats:p>","DOI":"10.1017\/s0963548323000445","type":"journal-article","created":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T05:49:44Z","timestamp":1701323384000},"page":"319-350","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["On minimum spanning trees for random Euclidean bipartite graphs"],"prefix":"10.1017","volume":"33","author":[{"given":"Mario","family":"Correddu","sequence":"first","affiliation":[]},{"given":"Dario","family":"Trevisan","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,11,30]]},"reference":[{"key":"S0963548323000445_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355562"},{"key":"S0963548323000445_ref27","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176994411"},{"key":"S0963548323000445_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-018-0837-x"},{"key":"S0963548323000445_ref1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005773"},{"key":"S0963548323000445_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-00321-4_19"},{"key":"S0963548323000445_ref9","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.98.030101"},{"key":"S0963548323000445_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125348"},{"key":"S0963548323000445_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/73393.73419"},{"key":"S0963548323000445_ref22","first-page":"148","volume-title":"Surveys in Combinatorics, 1989 (Norwich, 1989)","volume":"141","author":"McDiarmid","year":"1989"},{"key":"S0963548323000445_ref14","doi-asserted-by":"publisher","DOI":"10.1214\/16-AAP1239"},{"key":"S0963548323000445_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02394573"},{"key":"S0963548323000445_ref28","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176991596"},{"key":"S0963548323000445_ref13","unstructured":"[13] Christofides, N. (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Tech. rep. Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group."},{"key":"S0963548323000445_ref11","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.97.052109"},{"key":"S0963548323000445_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(99)00068-X"},{"key":"S0963548323000445_ref24","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1041903210"},{"key":"S0963548323000445_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288961"},{"key":"S0963548323000445_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"S0963548323000445_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90058-7"},{"key":"S0963548323000445_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0093472"},{"key":"S0963548323000445_ref26","first-page":"223","volume-title":"Mathematics and Computer Science II, Trends in Mathematics","author":"Steele","year":"2002"},{"key":"S0963548323000445_ref19","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1034968141"},{"key":"S0963548323000445_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01194923"},{"key":"S0963548323000445_ref10","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.012118"},{"key":"S0963548323000445_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(80)90045-6"},{"key":"S0963548323000445_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1985.10011"},{"key":"S0963548323000445_ref21","volume-title":"The Concentration of Measure Phenomenon","author":"Ledoux","year":"2001"},{"key":"S0963548323000445_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579135"},{"key":"S0963548323000445_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0367-4_2"},{"key":"S0963548323000445_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54075-2"},{"key":"S0963548323000445_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"S0963548323000445_ref25","unstructured":"[25] Riva, A. , Caracciolo, S. and Malatesta, E. (2018-2019) The random Minimum Spanning Tree problem. https:\/\/pcteserver.mi.infn.it\/~caraccio\/Lauree\/Riva.pdf."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548323000445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T10:18:28Z","timestamp":1712312308000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548323000445\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,30]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["S0963548323000445"],"URL":"https:\/\/doi.org\/10.1017\/s0963548323000445","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,30]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}