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: OAT S15/S16/S17
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.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2025 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