Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, August 26, 2010, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Stefan Schneider
Schöning discovered a simple local-search randomized algorithm for solving (d,k)-CSP, which still remains one of the fastest algorithms known so far. We discuss a modification to the algorithm where we arrange the d possible values of each variable on a search graph. This modification is due to Scheder, who improved the derandomization of Schöning's algorithm using search graphs. In this talk we will however show that for the randomized version any search graph that satisfies the symmetry property of distance-regularity gives us the same running time as the original algorithm by Schöning.
Thesis supervised by E. Welzl and R. Moser.
Automatic MiSe System Software Version 1.4803M | admin login