Tutte seminar - Laura Sanità

0/1 Polytopes with Quadratic Chvátal Rank

Abstract:

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]ⁿ, then it is known that O(n² 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 Ω(n²), 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ß.