Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 20, 2012, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Johannes Lengler
A function f on a finite state space is to be maximized. For such tasks, people often use Randomized Search Heuristics (RSHs). While these give simple algorithms and often yield good results in practice, the theory of RSHs is shamefully underdeveloped. The problem is that we lack definitions of what "good results in practice" are.
One approach is to compare the runtime of RSHs on a given problem with its "unrestricted Black Box Complexity", i.e., with the minimal expected number of evaluations of f that any algorithm needs. Unfortunately, this complexity turns out to be too small to be useful for many standard problems.
For this reason, several variations of the concept "Black Box Complexity" have been proposed. I will introduce the three main variants: "ranking-based Black Box Complexity", "unbiased Black Box Complexity" and "memory-restricted Black Box Complexity", and discuss their advantages and weaknesses.
Automatic MiSe System Software Version 1.4803M | admin login