No CrossRef data available.
Article contents
The Blind Passenger and the Assignment Problem
Published online by Cambridge University Press: 14 February 2011
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.
We introduce a discrete random process which we call the passenger model, and show that it is connected to a certain random model of the assignment problem and in particular to the so-called Buck–Chan–Robbins urn process. We propose a conjecture on the distribution of the location of the minimum cost assignment in a cost matrix with zeros at specified positions and remaining entries of exponential distribution. The conjecture is consistent with earlier results on the participation probability of an individual matrix entry. We also use the passenger model to verify a conjecture by V. Dotsenko on the assignment problem.
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2011
References
[1]Aldous, D. (2001) The ζ(2) limit in the random assignment problem. Random Struct. Alg. 18 381–418.Google Scholar
[2]Alm, S. E. and Sorkin, G. B. (2002) Exact expectations and distributions for the random assignment problem. Combin. Probab. Comput. 11 217–248.Google Scholar
[3]Buck, M. W., Chan, C. S. and Robbins, D. P. (2002) On the expected value of the minimum assignment. Random Struct. Alg. 21 33–58.Google Scholar
[4]Coppersmith, D. and Sorkin, G. B. (1999) Constructive bounds and exact expectations for the random assignment problem. Random Struct. Alg. 15 133–144.Google Scholar
[5]Dotsenko, V. S. (2000) Exact solution of the random bipartite matching model. J. Phys. A 33 (10), 2015–2030.CrossRefGoogle Scholar
[6]Frieze, A. M. (2004) On random symmetric travelling salesman problems. Math. Oper. Res. 29 878–890.Google Scholar
[7]Hessler, M. and Wästlund, J. (2009) LP-relaxed matching with free edges and loops. In ‘Optimization, matroids and error-correcting codes’, PhD thesis of M. Hessler, Linköping, Sweden.Google Scholar
[8]Hessler, M. and Wästlund, J. (2010) Edge cover and polymatroid flow problems. Electron. J. Probab. 15, 2200–2219.Google Scholar
[9]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
[10]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
[11]Linusson, S. and Wästlund, J. A generalization of the random assignment problem. arXiv:math.CO/0006146.Google Scholar
[12]Nair, C. (2005) Proofs of the Parisi and Coppersmith–Sorkin conjectures in the random assignment problem. PhD thesis, Stanford.Google Scholar
[13]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
[14]Parisi, G. (1998) A conjecture on random bipartite matching. arXiv:cond-mat/9801176.Google Scholar
[15]Wästlund, J. (2005) A proof of a conjecture of Buck, Chan and Robbins on the expected value of the minimum assignment. Random Struct. Alg. 26 237–251.Google Scholar
[16]Wästlund, J. (2005) Exact formulas and limits for a class of random optimization problems. Linköping Studies in Mathematics no. 5.Google Scholar
[17]Wästlund, J. (2005) The variance and higher moments in the random assignment problem. Linköping Studies in Mathematics no. 8.Google Scholar
[18]Wästlund, J. (2006) Random assignment and shortest path problems. In Proc. Fourth Colloquium on Mathematics and Computer Science, September 2006, Institut Élie Cartan, Nancy, France.Google Scholar
[19]Wästlund, J. (2009) An easy proof of the zeta(2) limit in the assignment problem. Electron. Comm. Probab. 14 261–269.Google Scholar
[20]Wästlund, J. (2010) The mean field traveling salesman and related problems. Acta Math. 204 91–150.Google Scholar
You have
Access
- 1
- Cited by