Publications

In der Informatik sind Prioritätswarteschlangen oder Priority Queues oft verwendete und etablierte Hilfsmittel, um in kurzer Zeit Objekte nach einer bestimmten Wichtung auszugeben. Auch aus diesem Grund haben Verbesserungen in diesem Bereich nichts von ihrer wissenschaftlichen Relevanz eingebüßt. Verschiedene Forschungseinrichtungen sind dabei diese Priority Queues effektiver oder auch nur einfacher zu gestalten. Dabei werden unterschiedliche Denkansätze verfolgt. Diese reichen von dynamischeren Baumstrukturen bis hin zu mehrteiligen Heaps. Die vorliegende Arbeit beschreibt und analysiert Ideen verschiedener Autoren aus den Jahren 2005 bis 2010 und führt einen Vergleich ausgewählter Arten an praktischen Beispielen durch. Die Algorithmen lassen sich hierbei nach den verschiedenen Baumstrukturen einteilen, auf denen sie aufgebaut sind. Daneben ist eine Unterteilung der Algorithmen nach ihrer Struktur möglich. Während bei einigen eine starre Struktur mit Markierungen genutzt wird, bieten andere Algorithmen die Möglichkeit die Struktur eingeschränkt oder auch zu großen Teilen zu variieren.

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 (base-2) and reflected Gray code representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using the reflected 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. For continuous multimodal functions, the algorithm also locates the global optimum in O((log n)2). Finally, we show that it is not possible for a black box algorithm to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).

We study two types of iterative 0/1-vertex-labeling processes in arbitrary network graphs where in each synchronous round every vertex - either never changes its label from 1 to 0, and changes its label from 0 to 1 if sufficiently many neighbours have label 1, - or changes its label if sufficiently many neighbours have a different label. In both scenarios the number of neighbours required for a change depends on individual threshold values of the vertices. Our contributions concern computational aspects related to the sets with minimum cardinality of vertices with initial label 1 such that during the process all vertices eventually change their label to 1 and remain with 1 as label. We establish hardness results for the general case and describe efficient algorithms for restricted instances.