0/1 Polytopes with Quadratic Chvátal Rank

0/1 Polytopes with Quadratic Chvátal Rank

0.00 Avg rating0 Votes
Article ID: iaor2017665
Volume: 65
Issue: 1
Start Page Number: 212
End Page Number: 220
Publication Date: Feb 2017
Journal: Operations Research
Authors: ,
Keywords: combinatorial optimization, heuristics
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] n , then it is known that O(n 2 log n) iterations always suffice and at least (1 + 1/eo(1))n iterations are sometimes needed, 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.

Reviews

Required fields are marked *. Your email address will not be published.