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

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 K_{n} and K_{m}. 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 H_{n} oracle calls for every grid USO, where H_{n} is the n-th Harmonic number. For the (n x 2)-grid (the n-ladder), an upper bound of 1.5*H_{n} 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*H_{n}.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 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