a1 Brown University and Ecole Normale Supérieure, DI ENS, CNRS UMR 8548, 45 rue d'Ulm, 75005 Paris, France (e-mail: firstname.lastname@example.org)
a2 Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA (e-mail: email@example.com)
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 n 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 c/n tends to a limiting function of c which is analytic for c ≤ 1/e, discontinuous at c = 1/e, and equal to 1 for c > 1/e. We further show that if the min mean weight is ≤ 1/(en), then the length of the relevant cycle is Θ p (1) (i.e., it has a limiting probability distribution which does not scale with n), but that if the min mean weight is > 1/(en), then the relevant cycle almost always has mean weight (1 + o(1))/(en) and length at least (2/π2 − o (1)) log2 n log log n.
(Received January 18 2012)
(Revised May 01 2013)
(Online publication July 22 2013)
2010 Mathematics subject classification:
† Work partly funded by NSF AF 0964037, and partly done while visiting Microsoft Research.