License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1348
URN: urn:nbn:de:0030-drops-13486
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1348/
Go to the corresponding Portal


Dietzfelbinger, Martin ; Rowe, Jonathan E. ; Wegener, Ingo ; Woelfel, Philipp

Tight Bounds for Blind Search on the Integers

pdf-format:
Document 1.pdf (284 KB)


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.

BibTeX - Entry

@InProceedings{dietzfelbinger_et_al:LIPIcs:2008:1348,
  author =	{Martin Dietzfelbinger and Jonathan E. Rowe and Ingo Wegener and Philipp Woelfel},
  title =	{{Tight Bounds for Blind Search on the Integers}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{241--252},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1348},
  URN =		{urn:nbn:de:0030-drops-13486},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1348},
  annote =	{Keywords: }
}

Seminar: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI