[Back]

M. Lackner:
"Detecting Structure in Permutations and Preferences";
Supervisor, Reviewer: R. Pichler, St. Szeider, G. Erdélyi; Institut für Informationssysteme, 2014; oral examination: 06-11-2014.

The detection and subsequent utilization of structure in data is a major theme in algorithm design. While many algorithmic problems are computationally hard on arbitrary data, real-world data often possesses characteristics -- structure -- that allow to speed up computation. A necessary first step is to identify structure; for this task efficient algorithms are required. This thesis considers structure detection in two particular forms of data: permutations and preferences. Algorithmic, complexity theoretic and combinatorial methods are used with the aim of establishing tools for efficiently detecting structure. Structure in permutations is studied in the form of permutation patterns. Detecting classical permutation patterns is NP-complete in general but requires only linear time for patterns of constant size. In this thesis, we explore the possibilities of detecting more general types of permutation patterns and show that these are considerably harder to detect than classical permutation patterns. For classical permutation patterns, we present a fast detection algorithm; the first to improve upon the exponential runtime of $O^*(2^n)$, which is required by brute-force search. Structure in preferences is studied in the form of domain restrictions. In computational social choice, domain restrictions are studied intensively as they often allow for efficient algorithms for otherwise intractable voting problems. Here, the detection of domain restrictions is a necessary precondition for their subsequent algorithmic utilization. This thesis considers the detection of structure in preferences from several viewpoints: First, we consider notions of distance to domain restrictions, which allow for more robust and flexible notions of structure. Although our results show that it is computationally hard to detect preferences which are only close to a domain restriction, we find efficient approximation and fixed-parameter algorithms solving this task. Second, we study single-peaked preferences (a particular form of domain restriction) in incomplete preferences. Here, depending on the exact notion of incompleteness, we find both intractable problems and fast algorithms. Finally, we mathematically connect permutation patterns with domain restrictions and thus establish a link between the two main concepts in this thesis. This link allows us to use methods from permutation patterns to identify combinatorial properties of domain restrictions. These results are the first to make precise statements about the likelihood of domain restrictions in random preferences. Also, we use this link to establish limits for the efficient detection of domain restrictions.

Die Erkennung und anschließende Nutzung von Struktur in Daten ist ein Kerngebiet des Algorithmenentwicklung. Während viele algorithmische Probleme im Allgemeinen rechenaufwändig sind, erlaubt die Strukturiertheit von Daten aus der realen Welt eine Beschleunigung der Rechenvorgänge. Ein notwendiger erster Schritt ist die Erkennung von Struktur, wofür effiziente Algorithmen erforderlich sind. Diese Dissertation beschäftigt sich mit der Erkennung von Struktur in zwei besonderen Arten von Daten: Permutationen und Präferenzen. Es werden Algorithmen, komplexitätstheoretische und kombinatorische Methoden verwendet mit dem Ziel, effiziente Mittel zur Strukturerkennung zur Verfügung zu stellen. Struktur in Permutationen wird in Form von Permutationsmustern untersucht. Das Erkennen von klassischen Permutationsmustern ist im Allgemeinen NP-vollständig, braucht aber nur lineare Zeit für Muster konstanter Länge. In dieser Arbeit erforschen wir die Möglichkeiten, noch allgemeinere Permutationsmuster zu erkennen, und zeigen, dass diese bedeutend schwieriger zu entdecken sind als klassische Muster. Für klassische Permutationsmuster präsentieren wir einen schnellen Erkennungsalgorithmus. Dies ist der erste Algorithmus, der die exponentielle Laufzeit von O*(2^n) unterbietet, die bei einer Brute-Force-Suche benötigt wird. Struktur in Präferenzen wird in Form von Domain-Restrictions untersucht. In Computational Social Choice werden Domain-Restrictions intensiv untersucht, da sie oft Algorithmen für Wahlprobleme ermöglichen, die andernfalls sehr aufwändig zu berechnen wären. Hier ist die Erkennung von Domain-Restrictions ein notwendiger erster Schritt für ihre darauffolgende algorithmische Nutzung. Diese Dissertation untersucht Struktur in Präferenzen aus verschiedenen Blickrichtungen: Erstens werden verschiedene Arten von Distanz zu Domain-Restrictions untersucht. Die Distanzmaße erlauben robustere und flexiblere Definitionen von Struktur in Präferenzen. Obwohl unsere Resultate zeigen, dass es sehr rechenintensiv ist zu überprüfen, ob Präferenzen nahe einer Domain-Restriction sind, finden wir effiziente Approximations- und parametrisierte Algorithmen, die diese Aufgaben lösen. Zweitens untersuchen wir single-peaked Präferenzen (dies ist eine bestimmte Form von Domain-Restriction) in unvollständigen Präferenzen. Hier finden wir, abhängig von der genauen Definition von Unvollständigkeit, sowohl schwer zu berechnende Probleme als auch effiziente Algorithmen. Abschließend verbinden wir Permutationsmuster mit Domain-Restrictions und schaffen hiermit eine Brücke zwischen den beiden großen Themenkomplexen dieser Dissertation. Diese Verbindung erlaubt, Methoden aus dem Gebiet der Permutationsmuster zu verwenden, um kombinatorische Eigenschaften von Domain-Restrictions zu finden. Diese Resultate erlauben, dass erstmals präzise Aussagen über die Häufigkeit von Domain-Restrictions in vollständig zufälligen Präferenzen getroffen werden. Darüber hinaus verwenden wir diese Verbindung, um auszuloten, bis zu welchem Grad eine effiziente Erkennung von Domain-Restrictions möglich ist.
Kurzfassung englisch
The detection and subsequent utilization of structure in data is a major theme in algorithm design. While many algorithmic problems are computationally hard on arbitrary data, real-world data often possesses characteristics - structure - that allow to speed up computation. A necessary first step is to identify structure; for this task efficient algorithms are required. This thesis considers structure detection in two particular forms of data: permutations and preferences. Algorithmic, complexity theoretic and combinatorial methods are used with the aim of establishing tools for efficiently detecting structure. Structure in permutations is studied in the form of permutation patterns. Detecting classical permutation patterns is NP-complete in general but requires only linear time for patterns of constant size. In this thesis, we explore the possibilities of detecting more general types of permutation patterns and show that these are considerably harder to detect than classical permutation patterns. For classical permutation patterns, we present a fast detection algorithm; the first to improve upon the exponential runtime of O*(2^n), which is required by brute-force search. Structure in preferences is studied in the form of domain restrictions. In computational social choice, domain restrictions are studied intensively as they often allow for efficient algorithms for otherwise intractable voting problems. Here, the detection of domain restrictions is a necessary precondition for their subsequent algorithmic utilization. This thesis considers the detection of structure in preferences from several viewpoints: First, we consider notions of distance to domain restrictions, which allow for more robust and flexible notions of structure. Although our results show that it is computationally hard to detect preferences which are only close to a domain restriction, we find efficient approximation and fixed-parameter algorithms solving this task. Second, we study single-peaked preferences (a particular form of domain restriction) in incomplete preferences. Here, depending on the exact notion of incompleteness, we find both intractable problems and fast algorithms. Finally, we mathematically connect permutation patterns with domain restrictions and thus establish a link between the two main concepts in this thesis. This link allows us to use methods from permutation patterns to identify combinatorial properties of domain restrictions. These results are the first to make precise statements about the likelihood of domain restrictions in random preferences. Also, we use this link to establish limits for the efficient detection of domain restrictions.