Tight bounds for blind search on the integers

dc.contributor.author	Dietzfelbinger, Martin	de
dc.contributor.author	Rowe, Jonathan E.	de
dc.contributor.author	Wegener, Ingo	de
dc.contributor.author	Woelfel, Philipp	de
dc.date.accessioned	2009-05-12T16:01:43Z
dc.date.available	2009-05-12T16:01:43Z
dc.date.issued	2008-01	de
dc.description.abstract	We analyze a simple random process in which a token is moved in the interval A = [0,n]: Fix a probability distribution µ over [1,n]. Initially, the token is placed in a random position in A. In round t, a random value d is chosen according to µ. If the token is in position a >= 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 µ, i.e., we show that min_µ{E_µ(T)} = Theta((log n)^2). 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.	en
dc.identifier.uri	http://hdl.handle.net/2003/26147
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-8724
dc.language.iso	en	de
dc.relation.ispartofseries	Reihe CI; 240-08	de
dc.subject	computational complexity	en
dc.subject	evolutionary algorithms	en
dc.subject	lower bounds	en
dc.subject.ddc	004	de
dc.title	Tight bounds for blind search on the integers	en
dc.type	Text	de
dc.type.publicationtype	report	de
dcterms.accessRights	open access

Files

Now showing 1 - 1 of 1