2009 | OriginalPaper | Buchkapitel
Average-Case Analyses of Vickrey Costs
verfasst von : Prasad Chebolu, Alan Frieze, Páll Melsted, Gregory B. Sorkin
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We explore the average-case “Vickrey” cost of structures in three random settings: the Vickrey cost of a shortest path in a complete graph or digraph with random edge weights; the Vickrey cost of a minimum spanning tree (MST) in a complete graph with random edge weights; and the Vickrey cost of a perfect matching in a complete bipartite graph with random edge weights. In each case, in the large-size limit, the Vickrey cost is precisely 2 times the (non-Vickrey) minimum cost, but this is the result of case-specific calculations, with no general reason found for it to be true.
Separately, we consider the problem of sparsifying a complete graph with random edge weights so that all-pairs shortest paths are preserved approximately. The problem of sparsifying a given graph so that for every pair of vertices, the length of the shortest path in the sparsified graph is within some multiplicative factor and/or additive constant of the original distance has received substantial study in theoretical computer science. For the complete digraph
${\vec{K}_n}$
with random edge weights, we show that
whp
Θ(
n
ln
n
) edges are necessary and sufficient for a spanning subgraph to give good all-pairs shortest paths approximations.