Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 23, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Leo Rüst
Some problems (e.g. the generalized linear complementarity problem) can be mapped to a unique sink orientation (USO) of a grid such that the solution to the problem corresponds to the unique sink of the grid. We are interested in the expected number of vertices a randomized algorithm needs to evaluate until it finds the sink, where a vertex evaluation returns the orientation of all incident edges.
In this talk, the focus will be on small grid-USOs and mainly on 2xn-grids, which we call "n-ladders". The hope is that the analysis of algorithms on ladders will yield new ideas for the general grid case.
Automatic MiSe System Software Version 1.4803M | admin login