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.
Automatic MiSe System Software Version 1.4803M | admin login