Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

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

**Duration**: This information is not available in the database

**Location**: CAB G51

**Speaker**: Bernd Gärtner

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: 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