{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T07:54:22Z","timestamp":1767858862459,"version":"3.49.0"},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2013,7,22]],"date-time":"2013-07-22T00:00:00Z","timestamp":1374451200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>The mean weight of a cycle in an edge-weighted graph is the sum of the cycle's edge weights divided by the cycle's length. We study the minimum mean-weight cycle on the complete graph on <jats:italic>n<\/jats:italic> vertices, with random i.i.d. edge weights drawn from an exponential distribution with mean 1. We show that the probability of the min mean weight being at most <jats:italic>c\/n<\/jats:italic> tends to a limiting function of <jats:italic>c<\/jats:italic> which is analytic for <jats:italic>c<\/jats:italic> \u2264 1\/<jats:italic>e<\/jats:italic>, discontinuous at <jats:italic>c<\/jats:italic> = 1\/<jats:italic>e<\/jats:italic>, and equal to 1 for <jats:italic>c<\/jats:italic> &gt; 1\/<jats:italic>e<\/jats:italic>. We further show that if the min mean weight is \u2264 1\/(<jats:italic>en<\/jats:italic>), then the length of the relevant cycle is \u0398<jats:italic><jats:sub>p<\/jats:sub><\/jats:italic>(1) (<jats:italic>i.e.<\/jats:italic>, it has a limiting probability distribution which does not scale with <jats:italic>n<\/jats:italic>), but that if the min mean weight is &gt; 1\/(<jats:italic>en<\/jats:italic>), then the relevant cycle almost always has mean weight (1 + <jats:italic>o<\/jats:italic>(1))\/(<jats:italic>en<\/jats:italic>) and length at least (2\/\u03c0<jats:sup>2<\/jats:sup> \u2212 <jats:italic>o<\/jats:italic> (1)) log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic> log log <jats:italic>n<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s0963548313000229","type":"journal-article","created":{"date-parts":[[2013,7,22]],"date-time":"2013-07-22T10:08:04Z","timestamp":1374487684000},"page":"763-782","source":"Crossref","is-referenced-by-count":4,"title":["The Min Mean-Weight Cycle in a Random Network"],"prefix":"10.1017","volume":"22","author":[{"given":"CLAIRE","family":"MATHIEU","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DAVID B.","family":"WILSON","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,7,22]]},"reference":[{"key":"S0963548313000229_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_33"},{"key":"S0963548313000229_ref16","unstructured":"van der Hofstad R. , Hooghiemstra G. and Van Mieghem P. (2006) Size and weight of shortest path trees with exponential link weights. Combin. Probab. Comput. 15 903\u2013926."},{"key":"S0963548313000229_ref20","unstructured":"Janson S. (1999) One, two and three times log n\/n for paths in a complete graph with random weights. Combin. Probab. Comput. 8 347\u2013361."},{"key":"S0963548313000229_ref8","unstructured":"Dasdan A. (2004) Experimental analysis of the fastest optimum cycle ratio and mean algorithms. ACM Trans. Des. Autom. Electron. Syst. 9 385\u2013418."},{"key":"S0963548313000229_ref14","doi-asserted-by":"crossref","unstructured":"Frieze A. M. and McDiarmid C. J. H. (1989) On random minimum length spanning trees. Combinatorica 9 363\u2013374.","DOI":"10.1007\/BF02125348"},{"key":"S0963548313000229_ref15","first-page":"1","volume-title":"ALENEX09: Workshop on Algorithm Engineering and Experiments","author":"Georgiadis","year":"2009"},{"key":"S0963548313000229_ref1","unstructured":"Aldous D. (1998) On the critical value for \u2018percolation\u2019 of minimum-weight trees in the mean-field distance model. Combin. Probab. Comput. 7 1\u201310."},{"key":"S0963548313000229_ref19","unstructured":"Janson S. (1987) Poisson convergence and Poisson processes with applications to random graphs. Stochastic Process. Appl. 26 1\u201330."},{"key":"S0963548313000229_ref21","unstructured":"Janson S. , Knuth D. E. , \u0141uczak T. and Pittel B. (1993) The birth of the giant component. Random Struct. Alg. 4 231\u2013358."},{"key":"S0963548313000229_ref25","unstructured":"Nair C. , Prabhakar B. and Sharma M. (2005) Proofs of the Parisi and Coppersmith\u2013Sorkin random assignment conjectures. Random Struct. Alg., 27 413\u2013444."},{"key":"S0963548313000229_ref3","doi-asserted-by":"crossref","unstructured":"Angel O. , Flaxman A. D. and Wilson D. B. (2012) A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks. Combinatorica 32 1\u201333.","DOI":"10.1007\/s00493-012-2552-z"},{"key":"S0963548313000229_ref27","doi-asserted-by":"crossref","unstructured":"Young N. E. , Tarjan R. E. and Orlin J. B. (1991) Faster parametric shortest path and minimum-balance algorithms. Networks 21 205\u2013221.","DOI":"10.1002\/net.3230210206"},{"key":"S0963548313000229_ref18","unstructured":"Hooghiemstra G. and Van Mieghem P. (2008) The weight and hopcount of the shortest path in the complete graph with exponential weights. Combin. Probab. Comput. 17 537\u2013548."},{"key":"S0963548313000229_ref23","doi-asserted-by":"crossref","unstructured":"Linusson S. and W\u00e4stlund J. (2004) A proof of Parisi's conjecture on the random assignment problem. Probab. Theory Rel. Fields 128 419\u2013440.","DOI":"10.1007\/s00440-003-0308-9"},{"key":"S0963548313000229_ref22","doi-asserted-by":"crossref","unstructured":"Koml\u00f3s J. , Major P. and Tusn\u00e1dy G. (1976) An approximation of partial sums of independent RV's, and the sample DF II. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 34 33\u201358.","DOI":"10.1007\/BF00532688"},{"key":"S0963548313000229_ref4","doi-asserted-by":"crossref","unstructured":"Arratia R. , Goldstein L. and Gordon L. (1989) Two moments suffice for Poisson approximations: The Chen\u2013Stein method. Ann. Probab. 17 9\u201325.","DOI":"10.1214\/aop\/1176991491"},{"key":"S0963548313000229_ref2","unstructured":"Aldous D. J. (2001) The \u03b6(2) limit in the random assignment problem. Random Struct. Alg., 18 381\u2013418."},{"key":"S0963548313000229_ref9","unstructured":"Ding J. (2011) Scaling window for mean-field percolation of averages. Ann. Probab., to appear. arXiv:1110.3361"},{"key":"S0963548313000229_ref12","unstructured":"Frieze A. (2004) On random symmetric travelling salesman problems. Math. Oper. Res. 29 878\u2013890."},{"key":"S0963548313000229_ref5","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s B. , Gamarnik D. , Riordan O. and Sudakov B. (2004) On the value of a random minimum weight Steiner tree. Combinatorica 24 187\u2013207.","DOI":"10.1007\/s00493-004-0013-z"},{"key":"S0963548313000229_ref11","unstructured":"Frieze A. M. (1985) On the value of a random minimum spanning tree problem. Discrete Appl. Math. 10 47\u201356."},{"key":"S0963548313000229_ref26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609589"},{"key":"S0963548313000229_ref13","unstructured":"Frieze A. M. and Grimmett G. R. (1985) The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math. 10 57\u201377."},{"key":"S0963548313000229_ref10","doi-asserted-by":"crossref","unstructured":"Flajolet P. , Knuth D. E. and Pittel B. (1989) The first cycles in an evolving graph. Discrete Math. 75 167\u2013215.","DOI":"10.1016\/0012-365X(89)90087-3"},{"key":"S0963548313000229_ref24","volume-title":"Brownian Motion, Vol. 30 of Cambridge Series in Statistical and Probabilistic Mathematics","author":"M\u00f6rters","year":"2010"},{"key":"S0963548313000229_ref17","unstructured":"van der Hofstad R. , Hooghiemstra G. and Van Mieghem P. (2007) The weight of the shortest path tree. Random Struct. Alg., 30 359\u2013379."},{"key":"S0963548313000229_ref7","unstructured":"Corless R. M. , Gonnet G. H. , Hare D. E. G. , Jeffrey D. J. and Knuth D. E. (1996) On the Lambert W function. Adv. Comput. Math. 5 329\u2013359."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000229","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T20:04:32Z","timestamp":1556049872000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000229\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,22]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["S0963548313000229"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000229","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,22]]}}}