Publikationen

We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary and Gray representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using Gray code does so in O((log n)^2) steps. A (1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O((log n)^2). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Omega((log n)^2) holds regardless of the choice of mutation distribution. Finally, we show that it is not possible for a black box algorithms to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).

The retrieval problem is the problem of associating data with keys in a set. Formally, the data structure must store a function f : U -> {0,1}^r that has specified values on the elements of a given subset S of U, |S|=n, but may have any value on elements outside S. All known methods (e.g. those based on perfect hash functions), induce a space overhead of (n) bits over the optimum, regardless of the evaluation time. - We show that for any k query time O(k) can be achieved using space that is within a factor 1+exp(-k) of optimal, asymptotically for large n. The time to construct the data structure is O(n), expected. If we allow logarithmic evaluation time, the additive overhead can be reduced to O(log log n) bits whp. - Further, we note a general reduction that transfers the results on retrieval into analogous results on approximate membership, a problem traditionally addressed using Bloom filters. This makes it possible to get arbitrarily close to the lower bound. The evaluation procedures of our data structures are extremely simple. For the results stated above we assume free access to fully random hash functions. This assumption can be justified using extra space o(n) to simulate full randomness on a RAM.

We describe experimental results on an implementation of a dynamic dictionary. The basis of our implementation is dynamic perfect hashingъ as described by Dietzfelbinger et al. (SIAM J. Computing 23, 1994, pp. 738--761), an extension of the storage scheme proposed by Fredman et al. (J. ACM 31, 1984, pp. 538--544). At the top level, a hash function is used to partition the keys to be stored into several sets. On the second level, there is a perfect hash function for each of these sets. This technique guarantees O(1) worst-case time for lookup and expected O(1) amortized time for insertion and deletion, while only linear space is required. We study the practical performance of dynamic perfect hashing and describe improvements of the basic scheme. The focus is on the choice of the hash function (both for integer and string keys), on the efficiency of rehashing, on the handling of small buckets, and on the space requirements of the implementation.

Heriber