Bodo Manthey — Random Shortest Paths with Applications
| Time: | Wednesday, July 17th, 2013, 12:45-13:30 |
| Location: | Citadel, H311 |
Probabilistic analysis for metric optimization problems has mostly been conducted on random Euclidean instances, but little is known about metric instances drawn from distributions other than the Euclidean. This motivates our study of random metric instances for optimization problems obtained as follows: Every edge of a complete graph gets a weight drawn independently at random. The length of an edge is then the length of a shortest path (with respect to the weights drawn) that connects its two endpoints. We prove structural properties of the random shortest path metrics generated in this way and apply these to heuristics for the TSP and the k-center problem.