Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 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.

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