Some New Results on Random Points in the Unit Square

Friday, March 20, 2015 - 9:30am - 10:10am
Klaus 1116
Alan Frieze (Carnegie-Mellon University)
Suppose that we X1,X2,...Xn are chosen randomly from the unit square. (More generally from the unit cube in d dimensions).

We consider the following:

Paper 1: Travelling in randomly embedded random graphs.
1. If the points are joined by an edge with probability p, what can one say about the shortest path distance in this embedding of G(n.p) as compared to the Euclidean distance.

2. To what extent can the Beardwood, Halton, Hammersley theorem on the length of the shortest TSP tour be extended to this case?

Paper 2: Separating subadditive Euclidean functionals.
For many optimization problems we know that a.s. growth rate of the optimum value up to a constant, e.g. for TSP, Minimum Spanning Tree, Steiner Tree, Perfect Matching, 2-factor. We know that a.s. these optimum values are all within a constant factor of each other, but we do not in general know the constants and so the question arises as to whether different problems give rise to different constants. We prove that these constants are indeed different and give a negative computational consequence in respect of using the 2-factor approximation for solving the TSP via branch and bound.

Joint work with Wes. Pegden.