Average-Case Analyses of Vickrey Costs

DOI10.1007/978-3-642-03685-9_33MaRDI QIDQ3638896zbMATH OpenOpenAlexFDO

Authors Prasad Chebolu, Páll Melsted, Gregory B. Sorkin, Alan Frieze

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_33

zbMATH Keywords

average-case analysisminimum spanning treeMSTrandom assignment problemrandom graphshortest pathVCG auction

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Auctions, bargaining, bidding and selling, and other market models (91B26)

Recommendations

• Minimum-weight combinatorial structures under random cost-constraints
• First passage percolation on locally treelike networks. I. Dense random graphs
• First-passage percolation on a ladder graph, and the path cost in a VCG auction
• On Shortest Paths in Graphs with Random Weights
• scientific article; zbMATH DE number 1416161

Cited in

(3)

• First-passage percolation on a ladder graph, and the path cost in a VCG auction
• scientific article; zbMATH DE number 7650127 (Why is no real title available?)
• Successive minimum spanning trees

This page was built for publication: Average-Case Analyses of Vickrey Costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638896)