Scalable Algorithms for Problems in Large-Scale Combinatorial Structures

Wir studieren drei Probleme der kombinatorischen Optimierung und algorithmischer Geometrie im Rahmen des Algorithm Engineering: Das Lösen von Kanten Orientierungen, das Aufrechterhalten einer dynamischen konvexen Hülle und das Berechnen von Hypergraph Matchings.

In einem ungerichteten Graphen fragt das Kanten Orientierung-Problem nach einer Orientierung von jeder Kante, sodass die maximale Anzahl von ausgehenden Kanten minimiert wird. Dieses Problem betrachten wir in statischen und dynamischen Graphen, in welchen Kanten willkürlich hinzugefügt und entfernt werden.
Wir präsentieren neue Beweise und Lösungstechniken für den statischen, dynamisch-exakten und dynamisch-approximativen Fall und verbinden theoretische Ergebnisse mit praktikablen Implementierungen.
Wir entwickeln einen neuen pfadbasierten Algorithmus für den statisch-exakten Fall und den ersten exakten, dynamischen Algorithmus, der die optimale Orientierung während der gesamten Änderungssequenz aufrechterhält.
Im dynamisch-approximativen Fall ermöglichen wir eine praktische Implementierung eines bekannten Algorithmus von Chekuri et al., der sogenannte lambda-gerechte Orientierungen aufrechterhält.
Unsere Experimente zeigen, dass wir im statischen Fall die Laufzeit  um den Faktor 6.59 verbessern können, im dynamisch-exakten Fall einen 32 % schnelleren Algorithmus entwickelten und im dynamisch-approximativen Fall um einen Faktor von 112 schneller sind.

Wir studieren das dynamische Konvexe Hülle-Problem in der Ebene.
Hier ist die Menge der Punkte gefragt, die die kleinste konvexe Hülle aller aktuellen Punkte darstellt.
Wir studieren dies im Nur-Einfügen und volldynamischen Fall. Im letzteren können Punkte auch wieder entfernt werden.
Neben Folklore Algorithmen präsentieren wir sowohl eine nur-einfügen als auch volldynamischen  Algorithmus basierend auf der logarithmischen Methode.
Hierbei werden die Punkte in logarithmisch wachsenden Gruppen aufgeteilt.
Anfragen können in logarithmisch-quadratischer Zeitkomplexität beantwortet werden.
Wir untersuchen die Stabilität unserer und konkurrierender Methoden.
Unsere Methoden sind robust, unter anderem auch wenn Punkte mit gleichen Koordinaten auftreten.
Experimente in der Nur-Einfügen-Modus zeigen, dass unser Algorithmus für Instanzen mit großer Hülle, wie zum Beispiel Kreise, gut skaliert während naive Methoden überraschend gut auf realistischen Instanzen in beiden Modi funktionieren.
Im volldynamischen Fall sind unsere Methoden die präferierte Wahl, wenn es viele Änderungen gibt, oder wenn polynomial viele Punkte in der Hülle sind.

Ein Hypergraph Matching ist eine Teilmenge von Kanten in einem Hypergraphen, sodass maximal eine Kante pro Knoten ausgewählt wird.
Unsere Algorithmen für dieses Problem arbeiten im (halb-)streaming und parallelen Model.
Wir zeigen sowohl Approximationsgarantien als auch ihren Speicher und Laufzeitbedarf formal.
Der parallele Algorithmus arbeitet im CRCW PRAM Speichermodel.
Wir zeigen auch eine arbeitsoptimale Version im CREW Speichermodel.
Unsere halb-streaming Methoden reduzieren den Speicherbedarf um einen Faktor von 13 auf einem großen Datensatz. Der parallele Algorithmus, wenn er auf einer Grafikkarte ausgeführt wird, ist bis zu 76 mal schneller als Methoden, die nur auf dem Hauptprozessor laufen.

Diese Studien sind gesteuert durch den Algorithm Engineering Kreislauf, in dem theoretische Einsichten Implementierungen beeinflussen und durch Experimente Algorithmen überarbeitet werden.
Wir bewerten alle Ansätze auf großen Datensätzen gegen die bisher besten Algorithmen.
Unsere Experimente zeigen exzellente Skalierungsverhalten unserer neuen Methoden für alle drei Probleme auf realistischen und synthetischen Datensätzen.