Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
A Positive Semidefinite Approximation of the Traveling Salesman PolytopeAlgebra & Discrete Mathematics
|Speaker: ||Ellen Veomett, University of Michigan|
|Location: ||1147 MSB|
|Start time: ||Thu, Mar 2 2006, 12:10PM|
For many interesting convex bodies X, the membership question (is the
point p in X?) is difficult to answer. In an attempt to rectify this
situation, we look for another convex body which is "close" to X for which
the membership question is easy. We will present a construction which
produces a hierarchy of sets P_1, P_2, . . . each contained in X. Each
P_k is obtained as an intersection of a cone of positive semidefinite
quadratic forms with an affine space. If X is a 0-1 polytope of dimension
n, we can show that P_n = X, similar to construction results of Lasserre,
Lovasz and Schrijver, and Sherali and Adams.
In the particular case where X is the traveling salesman polytope on n
cities, T_n, we can give metric bounds. The traveling salesman polytope
can be easily described as the convex hull of the orbit of a particular
vector under an action of the symmetric group. We will show that if k is
no more than n/2, then the scaling of P_k by n/k+O(1/n) contains T_n.
Membership in P_k is computable in time polynomial in n, the degree of the
polynomial linear in k. If time permits, we will discuss facets of the
traveling salesman polytope which lie on the boundary of P_k.