Random assignment and shortest path problems

Johan Wästlund 1
1 MAI - Department of Mathematics
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 : minimum matching random tree
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

INSMI | TDS-MACS

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

57

Téléchargements de fichiers

174

Contact


archive-ouverte@inria.fr