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?