hide
Free keywords:
-
Abstract:
Given a polytope $P \subseteq \mathbb{R}^n$, the Chv\'atal-Gomory
procedure computes iteratively the integer hull $P_I$ of $P$. The
Chv\'atal rank of $P$ is the minimal number of iterations needed to
obtain $P_I$. It is always finite, but already the Chv\'atal rank of
polytopes in $\mathbb{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\'atal rank of a polytope
$P \subseteq [0,1]^n $ in the 0/1~cube is at most $6 n^3 \log n$ and prove
the linear upper and lower bound $n$ for the case $P\cap \mathbb{Z}^n
= \emptyset$.
