Name
Abstract | ||
|---|---|---|
We analyze a simple random process in which a token is moved in the interval A = {0, . . . , n}: Fix a probability distribution mu 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 p. 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 mu. More precisely, we show that min(mu){E-mu(T)} = circle minus ((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. |
Year | Venue | Keywords |
|---|---|---|
2008 | STACS 2008: PROCEEDINGS OF THE 25TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE | random process,evolutionary algorithms,probability distribution,computational complexity,data structure |
DocType | Volume | ISSN |
Journal | abs/0802.2852 | Dans Proceedings of the 25th Annual Symposium on the Theoretical
Aspects of Computer Science - STACS 2008, Bordeaux : France (2008) |
Citations | PageRank | References |
9 | 0.57 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Dietzfelbinger | 1 | 999 | 115.12 |
| Jonathan E. Rowe | 2 | 458 | 56.35 |
| Ingo Wegener | 3 | 2663 | 210.34 |
| Philipp Woelfel | 4 | 432 | 38.40 |