{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T01:43:10Z","timestamp":1787362990186,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000086","name":"Directorate for Mathematical and Physical Sciences","doi-asserted-by":"publisher","award":["DMS1362785"],"award-info":[{"award-number":["DMS1362785"]}],"id":[{"id":"10.13039\/100000086","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>Let $G_{n,p}$ be the standard Erd\u00f6s--R\u00e9nyi--Gilbert random graph and let $G_{n,n,p}$ be the random bipartite graph on $n+n$ vertices, where each $e\\in [n]^2$ appears as an edge independently with probability $p$. For a graph $G=(V,E)$, suppose that each edge $e\\in E$ is given an independent exponential rate 1 cost $X_e$. Let $C(G)$ denote the random variable equal to the length of the minimum cost perfect matching if $G$ contains at least one perfect matching, and let $C(G)=0$ otherwise. Let $\\mu(G)=\\textbf{E}{C(G)}$. We show that if $np\\gg{\\log}^{2}n$ and $G=G_{n,n,p}$, then with high probability (w.h.p.) $\\mu(G)\\approx\\frac{{\\pi}^2}{6p}$. This generalizes the well-known result for the case $G=K_{n,n}$, where $p=1$. We also show that if $G=G_{n,p}$, then $\\mu(G_{n,p}) \\approx\\frac{{\\pi}^2}{12p}$ w.h.p. along with concentration results for both types of random graph.<\/jats:p>","DOI":"10.1137\/15m1047672","type":"journal-article","created":{"date-parts":[[2017,3,7]],"date-time":"2017-03-07T12:00:39Z","timestamp":1488888039000},"page":"489-510","source":"Crossref","is-referenced-by-count":2,"title":["Minimum Cost Matching in a Random Graph with Random Costs"],"prefix":"10.1137","volume":"31","author":[{"given":"Alan","family":"Frieze","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tony","family":"Johansson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,3,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192719"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1015"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009825"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000024"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90058-7"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.37236\/1519"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070406"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399003892"},{"key":"atypb10","first-page":"1","author":"Karp R. M.","year":"1987","journal-title":"New York"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-003-0308-9"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20084"},{"key":"atypb13","unstructured":"G. Parisi,\n                      A Conjecture on Random Bipartite Matching\n                      , preprint,arXiv:cond-mat\/9801176, 1998."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02699376"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v13-1372"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v14-1475"},{"key":"atypb17","unstructured":"J. Wa\u0308stlund,\n                      A Simple Proof of the Parisi and Coppersmith-Sorkin Formulas for the Random Assignment Problem\n                      , Linko\u0308ping Studies in Mathematics 6, Linko\u0308ping University Electronic Press, Linko\u0308ping, (2005)."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90047-3"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"J. M. Steele,\n                      Probability Theory and Combinatorial Optimization\n                      , SIAM, Philadelphia, PA, 1996.","DOI":"10.1137\/1.9781611970029"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/0208036"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.2307\/3620251"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1047672","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:51:33Z","timestamp":1787320293000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1047672"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/15M1047672"],"URL":"https:\/\/doi.org\/10.1137\/15m1047672","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}