Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 27, 2016, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Antonis Thomas
Inspired by the Simplex algorithm for Linear Programming, we look at the behavior of some pivot rules on abstract cubes. In particular, we are interested in history-based rules: At every vertex decide on which vertex to go next based on the history (path) thus far. Arguably, the most well-known such rule is Zadeh's. This algorithm keeps a history of how many times each direction has been used; then, at every step it chooses the least used improving direction. In this talk, I will show examples of a few of history-based rules and review what is known about their behavior. The main strategy and challenges for designing lower bounds for them will then be discussed. For a specific one, known as Cunningham's rule, I will demonstrate a construction that forces it to take an exponentially long path.
Automatic MiSe System Software Version 1.4803M | admin login