No CrossRef data available.
Article contents
The Min Mean-Weight Cycle in a Random Network
Published online by Cambridge University Press: 22 July 2013
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
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)) log2n log log n.
Keywords
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2013
References
[1]Aldous, D. (1998) On the critical value for ‘percolation’ of minimum-weight trees in the mean-field distance model. Combin. Probab. Comput. 7 1–10.Google Scholar
[2]Aldous, D. J. (2001) The ζ(2) limit in the random assignment problem. Random Struct. Alg., 18 381–418.Google Scholar
[3]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–33.Google Scholar
[4]Arratia, R., Goldstein, L. and Gordon, L. (1989) Two moments suffice for Poisson approximations: The Chen–Stein method. Ann. Probab. 17 9–25.Google Scholar
[5]Bollobás, B., Gamarnik, D., Riordan, O. and Sudakov, B. (2004) On the value of a random minimum weight Steiner tree. Combinatorica 24 187–207.Google Scholar
[6]Chebolu, P., Frieze, A., Melsted, P. and Sorkin, G. B. (2009) Average-case analyses of Vickrey costs. In Approximation, Randomization, and Combinatorial Optimization (Dinur, I., Jansen, K., Naor, J. and Rolim, J., eds), Vol. 5687 of Lecture Notes in Computer Science, Springer, pp. 434–447.CrossRefGoogle Scholar
[7]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–359.Google Scholar
[8]Dasdan, A. (2004) Experimental analysis of the fastest optimum cycle ratio and mean algorithms. ACM Trans. Des. Autom. Electron. Syst. 9 385–418.Google Scholar
[9]Ding, J. (2011) Scaling window for mean-field percolation of averages. Ann. Probab., to appear. arXiv:1110.3361Google Scholar
[10]Flajolet, P., Knuth, D. E. and Pittel, B. (1989) The first cycles in an evolving graph. Discrete Math. 75 167–215.Google Scholar
[11]Frieze, A. M. (1985) On the value of a random minimum spanning tree problem. Discrete Appl. Math. 10 47–56.Google Scholar
[12]Frieze, A. (2004) On random symmetric travelling salesman problems. Math. Oper. Res. 29 878–890.Google Scholar
[13]Frieze, A. M. and Grimmett, G. R. (1985) The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math. 10 57–77.Google Scholar
[14]Frieze, A. M. and McDiarmid, C. J. H. (1989) On random minimum length spanning trees. Combinatorica 9 363–374.CrossRefGoogle Scholar
[15]Georgiadis, L., Goldberg, A. V., Tarjan, R. E. and Werneck, R. F. (2009) An experimental study of minimum mean cycle algorithms. In ALENEX09: Workshop on Algorithm Engineering and Experiments (Finocchi, I. and Hershberger, J., eds), SIAM, pp. 1–14.Google Scholar
[16]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–926.Google Scholar
[17]van der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2007) The weight of the shortest path tree. Random Struct. Alg., 30 359–379.Google Scholar
[18]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–548.Google Scholar
[19]Janson, S. (1987) Poisson convergence and Poisson processes with applications to random graphs. Stochastic Process. Appl. 26 1–30.Google Scholar
[20]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–361.Google Scholar
[21]Janson, S., Knuth, D. E., Łuczak, T. and Pittel, B. (1993) The birth of the giant component. Random Struct. Alg. 4 231–358.Google Scholar
[22]Komlós, J., Major, P. and Tusnády, G. (1976) An approximation of partial sums of independent RV's, and the sample DF II. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 34 33–58.Google Scholar
[23]Linusson, S. and Wästlund, J. (2004) A proof of Parisi's conjecture on the random assignment problem. Probab. Theory Rel. Fields 128 419–440.Google Scholar
[24]Mörters, P. and Peres, Y. (2010) Brownian Motion, Vol. 30 of Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press.Google Scholar
[25]Nair, C., Prabhakar, B. and Sharma, M. (2005) Proofs of the Parisi and Coppersmith–Sorkin random assignment conjectures. Random Struct. Alg., 27 413–444.Google Scholar
[26]Stanley, R. P. (1999) Enumerative Combinatorics 2, Vol. 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
[27]Young, N. E., Tarjan, R. E. and Orlin, J. B. (1991) Faster parametric shortest path and minimum-balance algorithms. Networks 21 205–221.Google Scholar
You have
Access
- 3
- Cited by