HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

On the Chvátal Rank of Polytopes in the 0/1 Cube

Alexander Bockmayr 1 Friedrich Eisenbrand Mark Hartmann Andreas S. Schulz
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Given a polytope $P\subseteq\R^n$, the Chvátal-Gomory procedure computes iteratively the integer hull $P_I$ of $P$. The Chvátal rank of $P$ is the minimal number of iterations needed to obtain $P_I$. It is always finite, but already the Chvátal rank of polytopes in $\R^2$ can be arbitrarily large. In this paper, we study polytopes in the 0/1~cube, which are of particular interest in combinatorial optimization. We show that the Chvátal rank of any polytope $P\subseteq [0,1]^n$ is $\mbox{O}(n^3 \log n)$ and prove the linear upper and lower bound $n$ for the case $P\cap \Z^n = \emptyset$.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00099018
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:41:34 AM
Last modification on : Friday, February 4, 2022 - 3:22:08 AM

Identifiers

  • HAL Id : inria-00099018, version 1

Collections

Citation

Alexander Bockmayr, Friedrich Eisenbrand, Mark Hartmann, Andreas S. Schulz. On the Chvátal Rank of Polytopes in the 0/1 Cube. Discrete Applied Mathematics, Elsevier, 1999, 98 (1-2), pp.21-27. ⟨inria-00099018⟩

Share

Metrics

Record views

57