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

Date and Time: Tuesday, March 30, 2010, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Bernd Gärtner

USO - What's new though?

A unique sink orientation (USO) is an orientation of the n-cube graph such that every nonempty face has a unique sink. USOs come up in various geometric and combinatorial contexts. The main algorithmic problem is to find the unique global sink. The computational model considered here is that of vertex evaluations: the algorithm may query arbitrary vertices in arbitrary order, and for every query vertex, an oracle returns the orientations of the incident edges. The complexity of a (randomized) algorithm in this model is the worst-case (expected) number of vertex evaluations that it needs in order to find the sink of an n-cube USO.

Nontrivial algorithms (deterministic and randomized) with complexity O(c^n) exist for values of c<2, but no subexponential bounds are known in the general case. The common weakness of the existing algorithms is that information obtained from earlier vertex evaluations is insufficiently reused. I will show that a very simple vertex recycling strategy already leads to a new best "understandable" randomized algorithm. By "understandable" I mean that the algorithm does not require the use of complex computer-generated strategies. The hope is that along these lines, we will be able to improve even over the currently best "non-understandable" algorithm.

Joint work with Jan Foniok and Lorenz Klaus from IFOR.

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