First-passage percolation on a ladder graph, and the path cost in a VCG auction

DOI10.1002/rsa.20328zbMath1213.60158OpenAlexW2163570670MaRDI QIDQ2998892

David Gamarnik, Abraham D. Flaxman, Gregory B. Sorkin

Publication date: 11 May 2011

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20328

zbMATH Keywords

random graphsfirst-passage percolationauction theory

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Random walks on graphs (05C81)

Related Items (2)

On the Markov Transition Kernels for First Passage Percolation on the Ladder ⋮ Asymptotics of First-Passage Percolation on One-Dimensional Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-passage percolation on width-two stretches with exponential link weights
• Percolation theory and first-passage percolation
• First-passage percolation on the square lattice
• A BGP-based mechanism for lowest-cost routing
• On certain connectivity properties of the internet topology
• FIRST-PASSAGE PERCOLATION ON THE RANDOM GRAPH
• The ?(2) limit in the random assignment problem
• Algorithmic mechanism design (extended abstract)
• Frugal path mechanisms
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• An upper bound for the velocity of first-passage percolation
• Incentives in Teams
• Lower and Upper Bounds for the Time Constant of First-Passage Percolation
• On the expected payment of mechanisms for task allocation

This page was built for publication: First-passage percolation on a ladder graph, and the path cost in a VCG auction