Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, October 27, 2016, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Antonis Thomas

Exponential paths for history-based pivot rules on abstract cubes

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login