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.
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
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

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

Collections

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〉

Partager

Métriques

Consultations de la notice

37

Téléchargements de fichiers

27