0/1 Polytopes with Quadratic Chvátal Rank
|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ß.
200 University Avenue West
Waterloo, ON N2L 3G1