Lower bounds and algorithms for covering sequences of subsets of a finite set

Abstract

In dieser Arbeit befassen wir uns mit der Verallgemeinerung von universal cycles zu covering sequences. Universal cycles sind kompakte Strings, die eine Klasse kombinatorischer Objekte kodieren. Eine P_n-covering sequence ist ein String, in dem jede Teilmenge von {1,...,n} als zusammenhängender Substring enthalten ist. Wir liefern neue untere Schranken für die minimale Länge von P_n-covering sequences sowie für verwandte Fragestellungen. Darüber hinaus geben wir Sätze an, mit denen sich untere Schranken für solche Strings gewinnen lassen, die einen vorgegebenen Substring enthalten; diese nutzen wir wiederum in einem rechnergestützten Ansatz, um die bekannten unteren Schranken weiter zu verbessern. Ferner leiten wir eine neuartige Reduktion auf das Generalised Traveling Salesperson Problem her und machen uns diese zunutze. Für einen alternativen Konstruktionsalgorithmus führen wir das Konzept der „pruning admissible“ Äquivalenzrelationen und Präordnungen ein. In einer modifizierten Variante von beam search, einem unvollständigen Baumsuchverfahren, werden pruning admissible Präordnungen zusammen mit Heuristiken eingesetzt, um den Suchraum erheblich zu verkleinern. Wir führen Experimente mit verschiedenen Heuristiken durch und wählen die beste für eine größere Versuchsreihe aus, die neue, bislang kürzeste P_n-covering sequences liefert.

In this thesis we focus on the generalisation of universal cycles to covering sequences. Universal cycles are compact strings encoding a class of combinatorial objects. A P_n-covering sequence is a string such that every subset of {1,...,n} is contained as a contiguous substring. We provide new lower bounds on the minimal length of P_n-covering sequences and related problems. Additionally theorems are given to obtain a lower bound on such sequences containing a predefined substring which we in turn use in a computational approach to further improve upon the known lower bounds. We derive and exploit a novel reduction to the Generalised Traveling Salesperson Problem. For an alternative construction algorithm, we introduce the concept of pruning admissible equivalence relations and preorders. In a modified variant of beam search, an incomplete tree search algorithm, pruning admissible preorders along with heuristics are then used to substantially reduce the search space. Experiments on different heuristics are run and the best heuristic is chosen for the algorithm in a bigger set of experiments, which yield new shortest-known P_n-sequences.