Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 19, 2013, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Bernd Gärtner
Fourier-Motzkin elimination for systems of inequalities is what Gauss elimination is for systems of equations. In this talk, I will first describe the (utterly simple) Fourier-Motzkin elimination procedure and then give two applications of it: (i) a proof of the Farkas Lemma underlying the linear programming duality theorem, and (ii) a polynomial-time algorithm for finding an integral solution of a system of inequalities with integral coefficients whose absolute values sum up to at most 2 in every left-hand side. The latter algorithm is due to Schrijver and (for example) yields another proof of the fact that the 2-SAT problem is in P.
Automatic MiSe System Software Version 1.4803M | admin login