For a polytope P, the Chvátal closure P0 P is obtained by simultaneously strengthening all feasible inequalities cx 6 (with integral c) to cx 6 bc. 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 On2 log n iterations always suffice and at least 1+1e o1n 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 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 k k1-norm of the normal vector defining P.

0/1 polytopes with quadratic Chvátal rank

Sanità, Laura
2017

Abstract

For a polytope P, the Chvátal closure P0 P is obtained by simultaneously strengthening all feasible inequalities cx 6 (with integral c) to cx 6 bc. 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 On2 log n iterations always suffice and at least 1+1e o1n 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 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 k k1-norm of the normal vector defining P.
2017
2016
Rothvoß, Thomas; Sanità, Laura
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/4063853
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact