Detailansicht
Algorithm engineering for cut problems
Alexander Noe
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Dr.-Studium der technischen Wissenschaften (DissG: Informatik)
Betreuer*in
Monika Henzinger
DOI
10.25365/thesis.69760
URN
urn:nbn:at:at-ubw:1-11122.96791.960032-6
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Graphen sind eine natürliche Representation von Daten aus zahlreichen Kontexten, zum Beispiel Verbindungen in sozialen Netzwerken, Web-Netzwerken, Straßennetzwerken und vielen weiteren. In den letzten Jahrzehnten sind viele dieser Netzwerke zu enormer Größe gewachsen, was effiziente Algorithmen zu ihrer Partitionierung in kleinere, eher begreifliche Teile erforderlich macht. In dieser Arbeit versuchen wir, die Knoten von Graphen in mehrere Blöcke zu partitionieren, so dass die Anzahl von Kanten, welche Blockgrenzen schneiden, minimiert wird. Es gibt eine Vielzahl von Schnitt- und Partitionierungsproblemen auf Graphen, welche Bereits seit Jahrzehnten erforscht werden. Diese Arbeit entwickelt hocheffiziente Algorithmen für das (Global) Minimum Cut Problem, das Balanced Graph Partitioning Problem und das Multiterminal Cut Problem. Alle hierbei entwickelten Algorithmen sind effizient in der Praxis und frei nutzbar. Im Einzelnen haben wir die folgenden Ergebnisse erzielt und Algorithmen entwickelt:
• Schnelle heuristische und exakte shared-memory parallele Algorithmen für das (Global) Minimum Cut Problem. Wir präsentieren
effiziente Implementierungen bestehender Methoden und kombinieren diese mit neuartigen Verfahren, um Algorithmen zu entwickeln, die einen minimalen Schnitt signifikant schneller finden können als der bisherige Stand der Forschung. Die heuristische Variante unseres Algorithmus hat hierbei auch eine deutlich niedrigere empirisch beobachtete Fehlerrate als bestehende inexakte Algorithmen für das Problem.
• Der erste praktisch effiziente Algorithmus, welcher alle global minimalen Schnitte eines Graphen findet und eine kompakte Cactus Graph Datenstruktur bildet, welche diese Schnitte repräsentiert. Unser Algorithmus findet alle minimalen Schnitte in Graphen mit bis zu mehreren Milliarden Kanten und mehreren Millionen minimalen Schnitten in wenigen Minuten. Mithilfe einer Vielzahl von Datenreduktionstechniken verbessern wir die Laufzeit von bestehenden Algorithmen um bis zu mehreren Größenordnungen. Ausgehend von der Cactus Graph Repräsentation sind wir auch in der Lage, den Most Balanced Minimum Cut in Laufzeit linear zur Größe des Kaktusgraphen zu finden.
• Ein fully-dynamic Minimum Cut Algorithmus, welcher effizient einen minimalen Schnitt eines Graphen unter Kanteneinfügungen und -löschungen aufrecht erhält. Während es bereits theoretische Forschung zu diesem Problem gibt, ist unser Algorithmus der erste implementierte fully-dynamic Algorithmus für das Problem. Unsere Arbeit nutzt die bestehenden theoretischen Grundlagen und kombiniert sie mit effizienten und fein abgestimmten Implementierungen, um zu einem Algorithmus zu gelangen, welcher um bis zu mehrere Größenordnungen schneller ist als Neuberechnung mit statischen Algorithmen.
• Eine Metaheuristik auf Basis von ganzzahliger linearer Optimierung für das Balanced Graph Partitioning Problem. Da ganzzahlige lineare Programme nicht für große Eingaben skalieren, definieren wir ein deutlich kleineres Modell, auf welchem wir das Problem unter Zuhilfenahme von Symmetry Breaking skalierbar machen. Dies resultiert in einer mächtigen Metaheuristik zur lokalen Suche, welche existierende hochqualitative Partitionierungen noch weiter verbessern kann. Wir binden diese Metaheuristik in einen existierenden evolutionären Algorithmus ein und erhalten so einen Algorithmus, der Partitionierung hoher Qualität selbst erzeugen kann.
• Ein shared-memory paralleler exakter Algorithmus für das Multiterminal Cut Problem. Für diesen branch-and-reduce Algorithmus entwickeln wir hocheffiziente Datenreduktionsregeln, um ein Problem in ein viel kleineres äquivalentes Problem umzuwandeln. Außerdem präsentieren wir einen inexakten Algorithmus, welcher hochqualitative Lösungen für extrem schwere Instanzen in annehmbarer Zeit liefert.
Abstract
(Englisch)
Graphs are a natural representation of data from various contexts, such as social connections, the web, road networks, and many more. In the last decades, many of these networks have become enormous, requiring efficient algorithms to cut networks into smaller, more readily comprehensible blocks. In this work, we aim to partition the vertices of a graph into multiple blocks while minimizing the number of edges that connect different blocks. There is a multitude of cut or partitioning problems that have been the focus of research for multiple decades. This work develops highly-efficient algorithms for the (global) minimum cut problem, the balanced graph partitioning problem and the multiterminal cut problem. All of these algorithms are efficient in practice and freely available for use. In particular, we obtain the following results and algorithms:
• Fast heuristic and exact shared-memory parallel algorithms for the (global) minimum cut problem. We present efficient implementations of existing techniques and combine them with novel approaches to give algorithms that find a minimum cut in huge networks significantly faster than state-of-the-art algorithms. Our heuristic algorithm has a lower empirically observed error rate than existing inexact algorithms for the problem.
• The first engineered algorithm that finds all (global) minimum cuts and returns a compact cactus graph data structure which represents all of them in graphs with billions of edges in a few minutes. With a multitude of data reduction techniques, we improve the running time of state-of-the-art algorithms by up to multiple orders of magnitude. Based on the representation of all minimum cuts, we are able to find the most balanced minimum cut in time linear to the size of the cactus graph.
• A fully-dynamic minimum cut algorithm that efficiently maintains the minimum cut on a graph under edge insertions and deletions. While there is theoretical work, our algorithm is the first implementation of a fully-dynamic algorithm for the problem. Our algorithm uses the theoretical foundation and builds on it with efficient and finely-tuned implementations to give an algorithm that gives up to multiple orders of magnitude speedup to static recomputation.
• An integer linear programming (ILP) based meta-heuristic for the balanced graph partitioning problem. As ILPs do not scale to large inputs, we define a much smaller model that allows us to use symmetry breaking and make the approach more scalable. This gives a powerful local search meta-heuristic that can improve given high-quality partitionings even further. We incorporate this meta-heuristic into an existing evolutionary algorithm to give an algorithm that computes state-of-the-art partitionings from scratch.
• A shared-memory parallel exact branch-and-reduce algorithm for the multiterminal cut problem. For this algorithm, we develop and engineer highly-efficient data reduction rules to transform a problem into a much smaller equivalent problem. Additionally we give an inexact algorithm that gives high-quality solutions for very hard problems in reasonable time.
Schlagwörter
Schlagwörter
(Englisch)
graph algorithm cut problem minimum cut global minimum cut multiterminal cut graph algorithm graph partitioning balanced graph partitioning
Schlagwörter
(Deutsch)
Graph Algorithmus Schnittprobleme minimaler Schnitt multiterminal Cut Graphpartitionierung
Autor*innen
Alexander Noe
Haupttitel (Englisch)
Algorithm engineering for cut problems
Paralleltitel (Deutsch)
Algorithm Engineering für Schnittprobleme
Publikationsjahr
2021
Umfangsangabe
xiv, 181 Seiten : Diagramme
Sprache
Englisch
Beurteiler*innen
Ulrik Brandes ,
Ulrich Meyer
AC Nummer
AC16439468
Utheses ID
59388
Studienkennzahl
UA | 786 | 880 | |