## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

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

 Mittagsseminar Talk Information

Date and Time: Tuesday, June 05, 2007, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Martin Dietzfelbinger (Technische Univ. Ilmenau)

## Blind search on the integers

Consider the following game, played on a segment of the integers: Given is a probability distribution mu on {1,...,n}. Start at a point R(0) chosen uniformly at random in {1,...,n}, then repeat the following steps, for t=1,2,3,... :
- Choose (a distance) D(t) from {1,...,n} randomly, according to mu;
- If D(t) <= R(t-1), let R(t)=R(t-1)-D(t) (use the step, walk towards 0), otherwise let R(t)=R(t-1) (can't use the step).
Obviously, the process R(0), R(1), R(2), ... has 0 as an absorbing state. Let T = min{t|R(t)=0}. The goal is to minimize the expectation E(T), by choosing mu as cleverly as possible. We give tight upper and lower bounds on E(T), for mu optimally chosen.

Features of the proof: The upper bound is easy. The lower bound has two interesting features: delayed decisions and a potential function argument.

Motivation: The game is a toy version of a randomized search heuristic for a black-box optimization problem, where one tries to find the minimum of a function f:{1,...,n}->N by jumping around in {1,...,n} by randomly chosen distances, accepting a step if it improves (decreases) the function value. The game represents the behaviour of the strategy in case f is unimodal.

Joint work with Jonathan Rowe, Ingo Wegener, and Philipp Woelfel.

Information for students and suggested topics for student talks