Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 26, 2023, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Bernhard von Stengel (London School of Economics and Political Science)
LP duality (the strong duality theorem of linear programming) and the minimax theorem for zero-sum games are considered "equivalent" in the sense that one can easily be proved from the other. However, the classic proof by Dantzig (1951) of LP duality from the minimax theorem is flawed. It needs an additional assumption of strict complementarity. We show that this assumption amounts to assuming the Lemma of Farkas, which proves LP duality directly. We fix this with a new, different proof, distilled from Adler (2013). Separately, we state a new strongly polynomial reduction of LP duality (and possible infeasibility) to a zero-sum game. This is a mostly expository talk on a rather general but fundamental topic and is not too technical.
Automatic MiSe System Software Version 1.4803M | admin login