Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, March 05, 2015, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Bernd Gärtner

Randomly climbing a ladder

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:   2024  2023  2022  2021  2020  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