ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

17. Control Theory and Optimization

1991 MS Classification: 49, 52, 90 Eisenbrand, Friedrich and Bockmayr, Alexander, MPI Informatik Saarbrücken, Germany On the Chvátal rank of polytopes in the 0/1 cube Given a polytope P ⊆ ℝ^{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 ℝ^{2} can be arbitrarily large. We prove an O(n^{3} log n) upper bound of the Chvátal rank of polytopes in the 0/1 cube, which are of particular interest in combinatorial optimization. Reference: Alexander Bockmayr, and Friedrich Eisenbrand, On the Chvátal Rank of Polytopes in the 0/1 Cube, Research Report , MPI-I-97-2-009