Tutte seminar - Laura Sanità

Friday, July 13, 2012 3:30 pm - 4:30 pm EDT (GMT -04:00)

0/1 Polytopes with Quadratic Chvátal Rank

Speaker: Laura Sanità
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158


For a polytope P, the Chvátal closure P'⊆P is obtained by simultaneously strengthening all feasible inequalities cx≤β (with integral c) to cx≤⌊β⌋. The number of iterations of this procedure that are needed until the integral hull of P is reached is called the Chvátal rank. If P⊆[0,1]n, then it is known that O(n2 log n) iterations always suffices (Eisenbrand and Schulz (1999)) and at least (1+1/e-0(1))n iterations are sometimes needed (Pokutta and Stauffer (2011)), leaving a huge gap between lower and upper bounds. We prove that there is a polytope contained in the 0/1 cube that has Chvátal rank Ω(n2), closing the gap up to a logarithmic factor. In fact, even a superlinear lower bound was mentioned as an open problem by numerous authors.

Joint work with Thomas Rothvoß.