Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Random assignment an ...
Conference paper

Random assignment and shortest path problems

Johan Wästlund (1)
(1) Department of Mathematics
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2005
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
Proceedings
DOI
10.46298/dmtcs.3504
License
https://about.hal.science/hal-authorisation-v1
Indicators
565
Views
495
Downloads

Random assignment and shortest path problems

Johan Wästlund (1)
(1) 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
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • minimum matching
  • random tree
Cited by

Source: OpenCitations

  • First passage percolation on random graphs with finite mean degrees

    The Annals of Applied Probability

    Authors : Shankar Bhamidi, Remco van der Hofstad, Gerard Hooghiemstra

    Journal reference : Volume 20, 2010, pp.

    DOI : 10.1214/09-aap666

  • Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks

    Advances in Applied Probability

    Authors : Shankar Bhamidi ORCID, Remco van der Hofstad ORCID, Gerard Hooghiemstra

    Journal reference : Volume 42, 2010, pp. 706-738

    DOI : 10.1017/s0001867800050412

  • Degree distribution of shortest path trees and bias of network sampling algorithms

    The Annals of Applied Probability

    Authors : Shankar Bhamidi ORCID, Jesse Goodman ORCID, Remco van der Hofstad ORCID, Júlia Komjáthy ORCID

    Journal reference : Volume 25, 2015, pp.

    DOI : 10.1214/14-aap1036

  • Weight of a link in a shortest path tree and the Dedekind Eta function

    Random Structures and Algorithms

    Authors : Piet Van Mieghem ORCID

    Journal reference : Volume 36, 2010, pp. 341-371

    DOI : 10.1002/rsa.20299

  • Random assignment problems

    European Journal of Operational Research

    Authors : Pavlo A. Krokhmal ORCID, Panos M. Pardalos ORCID

    Journal reference : Volume 194, 2007, pp. 1-17

    DOI : 10.1016/j.ejor.2007.11.062
Preview
Loading PDF preview...