Campus Event Calendar
Event Entry
What and Who
On the Chvatal-Rank of Polytopes in the 0/1 Cub
Friedrich Eisenbrand
Seminar des Graduiertenkollegs
AG 1, AG 2
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 15 December 97
16:00
60 Minutes
45 - FB14
015
Saarbrücken
Abstract
Given a polytope P, the Chvatal-Gomory procedure computes iteratively the integer hull P_I of P. The Chvatal-rank of P is the minimal number of iterations needed to obtain P_I. It is always finite, but already the Chvatal-rank of polytopes in R^2 can be arbitrarily large.In this talk, I discuss polytopes in the 0/1 cube, which are of particular interest in combinatorial optimization. I will present our result that the Chvatal-rank of a polytope P in the n-dimensional 0/1 cube is at most 6 n^3 log n.
This is joint work with Alexander Bockmayr.
Contact
--email hidden
passcode not visible
logged in users only