Random assignment and shortest path problems

Abstract : We explore a similarity between the $n$ by $n$ random assignment problem and the random shortest path problem on the complete graph on $n+1$ vertices. This similarity is a consequence of the proof of the Parisi formula for the assignment problem given by C. Nair, B. Prabhakar and M. Sharma in 2003. We give direct proofs of the analogs for the shortest path problem of some results established by D. Aldous in connection with his $\zeta (2)$ limit theorem for the assignment problem.
Keywords :
Type de document :
Communication dans un congrès
Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.31-38, 2006, DMTCS Proceedings
Domaine :

Littérature citée [14 références]

https://hal.inria.fr/hal-01184708
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 14:24:54
Dernière modification le : jeudi 11 mai 2017 - 01:02:51
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:10:07

Fichier

dmAG0102.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

• HAL Id : hal-01184708, version 1

Citation

Johan Wästlund. Random assignment and shortest path problems. Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.31-38, 2006, DMTCS Proceedings. 〈hal-01184708〉

Métriques

Consultations de la notice

57

Téléchargements de fichiers