TY - GEN

T1 - 0/1 Polytopes with quadratic Chvátal rank

AU - Rothvoß, Thomas

AU - Sanitá, Laura

PY - 2013

Y1 - 2013

N2 - For a polytope P, the Chvátal closure P′ ⊆ P is obtained by simultaneously strengthening all feasible inequalities cx ≤ β (with integral c) to cz ≤ ⌊β⌋. 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 suffice (Eisenbrand and Schulz (1999)) and at least (1 + 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 Ω(n2), 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.

AB - For a polytope P, the Chvátal closure P′ ⊆ P is obtained by simultaneously strengthening all feasible inequalities cx ≤ β (with integral c) to cz ≤ ⌊β⌋. 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 suffice (Eisenbrand and Schulz (1999)) and at least (1 + 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 Ω(n2), 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.

UR - http://www.scopus.com/inward/record.url?scp=84875497630&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-36694-9_30

DO - 10.1007/978-3-642-36694-9_30

M3 - Conference contribution

AN - SCOPUS:84875497630

SN - 9783642366932

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 349

EP - 361

BT - Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Proceedings

T2 - 16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013

Y2 - 18 March 2013 through 20 March 2013

ER -