On the Chvatal Closure of a Strictly Convex Body

ACO Student Seminar
Wednesday, February 10, 2010 - 1:30pm for 1 hour (actually 50 minutes)
ISyE Executive Classroom
Daniel Dadush – ISyE ACO, Georgia Tech
Sarah Fletcher
The analysis of Chvatal Gomory (CG) cuts and their associated closure for polyhedra was initiated long ago in the study of integer programming. The classical results of Chvatal (73) and Schrijver (80) show that the Chvatal closure of a rational polyhedron is again itself a rational polyhedron. In this work, we show that for the class of strictly convex bodies the above result still holds, i.e. that the Chvatal closure of a strictly convex body is a rational polytope.This is joint work with Santanu Dey (ISyE) and Juan Pablo Vielma (IBM).