Campus Event Calendar
Event Entry
What and Who
On the Chvatal Rank of Polytopes in the 0/1 Cube
Fritz Eisenbrand
AG2
AG2 Working Group Seminar
AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 17 September 97
11:15
60 Minutes
46.1
024
Saarbrücken
Abstract
Given a polytope P, the Chvatal-Gomory procedure computes iteratively the integer hull PI of P. The Chvatal Rank of P is the minimal number of iterations needed to obtain PI. It is always finite, but already the rank of polytopes in R^2 can be arbitrarily large. We show that the Chvatal Rank of Polytopes in the 0/1 cube, which are of particular interest in combinatorial optimization, is at most 6n^3 log n, where n is the dimension of the cube. In the proof we use only elementary geometry and elementary number theory.
Contact
Uwe Waldmann
9325-227
--email hidden
passcode not visible
logged in users only