The University of Michigan Combinatorics Seminar
Fall 2006
November 3, 4:10-5:00, 3866 East Hall

The computational complexity of convex bodies

Ellen Veomett

University of Michigan


For convex bodies associated to many interesting and important questions, deciding whether a given point is a member of the body is computationally hard. Thus, one looks for an approximating body for which deciding membership is computationally feasible. In this talk, I will discuss using polytopes, projections of polytopes, and sections of the cone of positive semidefinite quadratic forms to approximate convex bodies. I will discuss in particular the case where the set approximated is the Traveling Salesman Polytope.