Average-Case Analyses of Vickrey Costs

DOI10.1007/978-3-642-03685-9_33zbMath1255.91140OpenAlexW1520499261MaRDI QIDQ3638896

Prasad Chebolu, Gregory B. Sorkin, Páll Melsted, Alan M. 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

MSTshortest pathrandom graphminimum spanning treeaverage-case analysisrandom assignment problemVCG auction

Mathematics Subject Classification ID

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

Related Items (2)

Successive minimum spanning trees ⋮ Unnamed Item

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