Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 05, 2015, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Bernd Gärtner
For the purpose of this talk, the (n x m)-grid is the Cartesian graph product of Kn and Km. This can be visualized as a 'normal' grid with n rows and m columns, where in each row and column, all vertices are pairwise connected, not only the neighboring ones. A grid USO is an orientation of the (n x m)-grid with the property that every subgrid has a unique sink. A subgrid is induced by all vertices in some rows and columns. We are interested in finding the unique global sink when the grid USO is implicitly given by an oracle that returns for any given vertex the orientations of the n+m-2 incident edges. The complexity of an algorithm is the maximum (expected) number of oracle calls necessary to find the sink.
For the (n x 1)-grid, the (directed) random walk with random start vertex is the best possible randomized algorithm, with an expected number of Hn oracle calls for every grid USO, where Hn is the n-th Harmonic number. For the (n x 2)-grid (the n-ladder), an upper bound of 1.5*Hn is easy to get, but it was open for some time whether this is best possible.
In this talk, I will present and analyze an algorithm for the n-ladder, due to Dominik Scheder, with input from various people at the GWOP 2013 workshop. The expected number of oracle calls of this algorithm is bounded by 1.307*Hn.
Automatic MiSe System Software Version 1.4803M | admin login