Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 08, 2008, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Jiří Matoušek (Charles Univ., Prague)
LP-type problems is a successful axiomatic framework for optimization problems capturing, e.g., linear programming and the smallest enclosing ball of a point set. With Petr Škovroň we proved that in order to remove degeneracies of an LP-type problem, we sometimes have to increase its combinatorial dimension by a multiplicative factor of at least 1+epsilon for a certain small positive constant epsilon. The proof went by checking the unsolvability of a system of linear inequalities, with several pages of calculations. Here I will discuss a short topological proof showing that the dimension sometimes has to increase at least twice.
Automatic MiSe System Software Version 1.4803M | admin login