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

Date and Time: Tuesday, December 01, 2020, 12:15 pm

Duration: 30 minutes

Location: Zoom: conference room

Speaker: Simon Weber

Unique Sink Orientations: Constructions and Random Facet

Sink-finding in Unique Sink Orientations (USOs) is an abstraction for key optimization problems like Linear Programming, the Linear Complementarity Problem, or the Smallest Enclosing Ball Problem. The most promising algorithm for sink-finding is the Random Facet algorithm, as it is the only currently known candidate that may still have subexponential worst-case runtime. While the algorithm is well-understood on acyclic USOs, there is a large gap between known lower and upper bounds on the worst-case runtime on cyclic USOs.

In this work, we pursue a better understanding of the runtime of Random Facet on possibly cyclic USOs. To this end, we research USO constructions which might lead to a better lower bound. We prove that product constructions, which encompass almost all known USO constructions, do not allow us to construct USOs on which Random Facet takes more than subexponential time. Furthermore, we find a new USO construction, the bowed isomorphic extension, which is based on patterns seen in low-dimensional worst-case inputs to Random Facet. This new construction extends a bowed USO by one dimension by connecting it to an isomorphic copy of itself, which can be shown to preserve oddity and admit a nice recursive structure. While we do not understand the runtime of Random Facet on bowed isomorphic extensions yet, this new construction significantly extends our toolbox for creating bad inputs for Random Facet. The USOs created by bowed isomorphic extensions cannot be constructed using any previously known constructions.

Master Thesis supervised by Bernd Gärtner

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

Previous talks by year:   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