Full metadata record
DC FieldValueLanguage
dc.contributor.authorDietzfelbinger, Martinde
dc.contributor.authorRowe, Jonathan E.de
dc.contributor.authorWegener, Ingode
dc.contributor.authorWoelfel, Philippde
dc.description.abstractWe 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.relation.ispartofseriesReihe CI; 240-08de
dc.subjectcomputational complexityen
dc.subjectevolutionary algorithmsen
dc.subjectlower boundsen
dc.titleTight bounds for blind search on the integersen
dcterms.accessRightsopen access-
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
24008.pdfDNB219.79 kBAdobe PDFView/Open

This item is protected by original copyright

This item is protected by original copyright rightsstatements.org