0/1 Polytopes with Quadratic Chvatal Rank

• 成果类型: Article
• 署名作者: Rothvoss, Thomas; Sanita, Laura
• 署名单位: University of Washington; University of Washington Seattle; University of Waterloo
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2016.1549
• 发表日期: 2017
• 页码: 212-220
• 关键词: relaxations; optimization; hierarchy; closure; bounds

摘要

For a polytope P, the Chvatal closure P ' subset of P is obtained by simultaneously strengthening all feasible inequalities cx <= beta (with integral c) to cx <= left perpendicular beta right perpendicular. 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 subset of [0,1](n), then it is known that O(n(2) log n) iterations always suffice and at least (1+1/e - o(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 Chvatal rank Omega(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 Chvatal rank to simultaneous Diophantine approximations w.r.t. the parallel to. parallel to(1)-norm of the normal vector defining P.