Autor(en): | Dietzfelbinger, Martin Rowe, Jonathan E. Wegener, Ingo Woelfel, Philipp |
Titel: | Tight bounds for blind search on the integers |
Sprache (ISO): | en |
Zusammenfassung: | 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. |
Schlagwörter: | computational complexity evolutionary algorithms lower bounds |
URI: | http://hdl.handle.net/2003/26147 http://dx.doi.org/10.17877/DE290R-8724 |
Erscheinungsdatum: | 2008-01 |
Enthalten in den Sammlungen: | Sonderforschungsbereich (SFB) 531 |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
24008.pdf | DNB | 219.79 kB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource ist urheberrechtlich geschützt. |
Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org