2012/04/20 by Thomas Rothvoss, Thomas Rothvoß, Laura Sanità +3 · 1 citation
Computer Science · Mathematics · #52B11 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Point processes and geometric inequalities #cs.CG #cs.DM #math.CO #msc:52B11
paper · pdf · doi:10.48550/arxiv.1204.4753
15 pages, 2 figures
arxiv created 2012/04/20 · openalex publication_date 2012/04/20 · arxiv updated 2012/04/27 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
For a polytope P, the Chvatal closure P' is obtained by simultaneously strengthening all feasible inequalities cx <= b (with integral c) to cx <= floor(b). The number of iterations of this procedure that are needed until the integral hull of P is reached is called the Chvatal rank. If P is a subset of [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 Chvatal rank Omega(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 Chvatal rank to simultaneous Diophantine approximations w.r.t. the L1-norm of the normal vector defining P.