## Bodo Manthey — *Random Metrics and Shortest Paths*

Time: | Wednesday, November 23, 2011 |

Location: | Room 101, Citadel |

Many optimization problems are defined on a metric space. If this space is a Euclidean space,
then it is easy to define what a random instance is. Unfortunately, it seems to be much
more difficult to define a notion of a "random metric space".
We consider the following approach: Given a complete graph on *n* vertices, we draw
a length *w*(*e*) for every edge *e* = {*u*, *v*} independently and uniformly
from the interval [0,1].
Then the distance *d*(*e*) between *u* and *v* is the length of the shortest
path with respect to *w* that connects *u* and *v*.

We show that the length of the longest edge in this model is *O*(log(*n*)/*n*) with high
probability and in expectation.
Furthermore, we raise the following questions:
How does the probability distribution of a single edge look like? What are the dependencies between (non-)adjacent edges?
What is the expected approximation ratio of a simple greedy algorithm for matching?
What is the expected approximation ratio of the 2-opt heuristic for the traveling salesman problem?