Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 19, 2012, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Komei Fukuda
For a given system of $m$ linear inequalities in $d$ variables, the (polyhedral) redundancy removal problem is to find an equivalent non-redundant system. The problem is obviously polynomially solvable via linear programming. Yet, in practice, it is quite challenging to remove redundancies from a randomly generated system of not-so-large size, say in dimension $10$ and $1$ million inequalities, even with the best known method due to Ken Clarkson. In this talk, we use the LP complexity to measure the hardness of this problem and review Clarkson's algorithm. The open problem is as to whether there is an algorithm to beat the LP complexity of Clarkson's algorithm.
Automatic MiSe System Software Version 1.4803M | admin login