| 22. Tight Bounds for Blind Search on the Integers (2008) | |||||||||||||
Abstract | |||||||||||||
| We analyze a simple random process in which a token is moved in the interval $A={0,dots,n$: Fix a probability distribution $mu$ over ${1,dots,n$. Initially, the token is placed in a random position in $A$. In round $t$, a random value $d$ is chosen according to $mu$. If the token is in position $ageq d$, then it is moved to position $a-d$. Otherwise it stays put. Let $T$ be the number of rounds until the token reaches position 0. We show tight bounds for the expectation of $T$ for the optimal distribution $mu$. More precisely, we show that $min_mu{E_mu(T)=Thetaleft((log n)^2 ight)$. For the proof, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over $[0,1]$ with a ``blind'' optimization strategy.. @InProceedings{dietzfelbinger_et_al:LIPIcs:2008:1348, author = {Martin Dietzfelbinger and Jonathan E. Rowe and Ingo Wegener and Philipp Woelfel}, title = {22. Tight Bounds for Blind Search on the Integers}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)}, pages = {241--252}, series = {Leibniz International Proceedings in Informatics}, year = {2008}, volume = {1}, editor = {Susanne Albers and Pascal Weil}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany}, address = {Dagstuhl, Germany}, URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1348}, URN = {urn:nbn:de:0030-drops-13486}, annote = {Keywords: } } | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||