Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.