Campus Event Calendar
Event Entry
What and Who
Cutting Plane Proofs and Chvatal-Rank
Friedrich Eisenbrand
Max-Planck-Institut für Informatik, Saarbrücken, Germany
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, 18 May 98
16:00
60 Minutes
45
016
Saarbrücken
Abstract
The Chvatal-Gomory procedure, to compute the integer hull of a
polyhedron, can be used to prove unsatisfiability of propositional
formulas. The procedure then delivers a so called cutting plane proof
of the unsatisfiability. The length of such a cutting plane proof is
connected to the Chvatal rank of the underlying Polytope.
In this talk I will introduce the subject and present some
observations I came across.
Contact
Ülkü Coruh
9325-526
--email hidden
passcode not visible
logged in users only