TY - GEN

T1 - Average-case analyses of Vickrey costs

AU - Chebolu, Prasad

AU - Frieze, Alan

AU - Melsted, Páll

AU - Sorkin, Gregory B.

PY - 2009

Y1 - 2009

N2 - 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 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.

AB - 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 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.

KW - Average-case analysis

KW - Minimum spanning tree

KW - MST

KW - Random assignment problem

KW - Random graph

KW - Shortest path

KW - VCG auction

UR - http://www.scopus.com/inward/record.url?scp=70350594718&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03685-9_33

DO - 10.1007/978-3-642-03685-9_33

M3 - Conference contribution

AN - SCOPUS:70350594718

SN - 3642036848

SN - 9783642036842

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 434

EP - 447

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009

Y2 - 21 August 2009 through 23 August 2009

ER -