Combinatorics Seminar
Alan Frieze
Carnegie Mellon
Some new results on random points in the unit square
Abstract: Suppose that 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.
Monday March 2, 2015 at 3:00 PM in SEO 427