0/1 Polytopes with Quadratic Chvátal Rank

For a polytope

P

, the

Chvátal closure

P

′ ⊆ 

P

is obtained by simultaneously strengthening all feasible inequalities

cx

 ≤ 

β

(with integral

c

) to

$cx \leq \lfloor\beta\rfloor$

. 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

(

n

2

log

n

) iterations always suffice (Eisenbrand and Schulz (1999)) and at least

$(1+\frac{1}{e}-o(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

2

), closing the gap up to a logarithmic factor. In fact, even a superlinear lower bound was mentioned as an open problem by several authors. Our choice of

P

is the convex hull of a semi-random Knapsack polytope and a single fractional vertex. The main technical ingredient is linking the Chvátal rank to

simultaneous Diophantine approximations

w.r.t. the ∥ · ∥ 

1

-norm of the normal vector defining

P

.