Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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.

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