Detailansicht

Faster approximation algorithms for partially dynamic shortest path problems

Sebastian Krinninger

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 (Dissertationsgebiet: Informatik, IK: Computer-unterstützte Optimierung)

Betreuer*innen

Monika Henzinger ,

Georg Pflug

Volltext herunterladen
Volltext in Browser öffnen

DOI

10.25365/thesis.37358

URN

urn:nbn:at:at-ubw:1-29519.25336.735962-7

Link zu u:search

(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract

(Deutsch)

Ein Algorithmus heißt dynamisch wenn seine Eingabe mit der Zeit immer wieder Änderungen unterworfen ist und er deshalb das Ergebnis seiner Berechnungen regelmäßig anpasst. Das Hauptziel ist es, schneller zu sein als ein naiver Algorithmus, der das Ergebnis nach jeder Änderung von Grund auf neu berechnet. Für Graphalgorithmen bestehen die Änderungen in der Regel aus Kanteneinfügungen und -löschungen. In dieser Arbeit konzentrieren wir uns auf partiell-dynamische Algorithmen, die nur eine Art von Änderungen erlauben; entweder Einfügungen (inkrementelles Modell) oder Löschungen (dekrementelles Modell). Wir entwickeln schnellere Approximationsalgorithmen für gewisse Varianten des partiell-dynamischen Kürzeste Wege Problems in Bezug auf die Gesamtlaufzeit, also die Summe der Laufzeiten, die jeweils benötigt wird, um das Ergebnis nach einer Änderung zu aktualisieren. Als Ergebnis dieser Arbeit erhalten wir folgende Approximationsalgorithmen: (1) Einen randomisierten Algorithmus für das dekrementelle paarweise Kürzeste Wege Problem in ungewichteten ungerichteten Graphen, der sowohl einen multiplikativen Fehler von 1+ε als auch einen additiven Fehler von 2 hat und dessen Gesamtlaufzeit \tilde O(n^{5/2}) beträgt. (2) Einen deterministischen Algorithmus für das dekrementelle paarweise Kürzeste Wege Problem in ungewichteten ungerichteten Graphen mit multiplikativem Fehler 1+ε und Gesamtlaufzeit O(mn log n). (3) Einen randomisierten Algorithmus für das dekrementelle Kürzeste Wege Problem mit Startknoten in gewichteten ungerichteten Graphen mit multiplikativem Fehler 1+ε und Gesamtlaufzeit O(m^{1 + o(1)}). (4) Einen randomisierten Algorithmus für das dekrementelle Erreichbarkeitsproblem mit Startknoten in gerichteten Graphen mit Gesamtlaufzeit o(mn) sowie eine Erweiterung der Methode für das dekrementelle Kürzeste Wege Problem mit Startknoten in gewichteten gerichteten Graphen, ebenfalls mit Gesamtlaufzeit o(mn). (5) Einen deterministischen Algorithmus für das inkrementelle Kürzeste Wege Problem mit Startknoten in ungewichteten ungerichteten Graphen mit multiplikativem Fehler 1+ε und Gesamtlaufzeit O(m^{3/2} n^{1/2}) sowie eine Erweiterung der Methode für sowohl einen inkrementellen als auch einen dekrementellen Algorithmus für das Kürzeste Wege Problem mit Startknoten im CONGEST-Modell für verteiltes Rechnen.

Abstract

(Englisch)

We call an algorithm dynamic if it regularly updates the result of its computations as the input undergoes changes over time. The primary goal is to be faster than the naive algorithm that recomputes the result from scratch after each change. In graph algorithms / the changes to the input graph are usually edge insertions or deletions. In this thesis we focus on partially dynamic graph algorithms where only one type of updates is allowed; either insertions (incremental model) or deletions (decremental model).

Autor*innen

Sebastian Krinninger

Haupttitel (Englisch)

Faster approximation algorithms for partially dynamic shortest path problems

Paralleltitel (Deutsch)

Schnellere Approximationsalgorithmen für Partiell-Dynamische Kürzeste Wege Probleme

Paralleltitel (Englisch)

Faster approximation algorithms for partially dynamic shortest path problems

Publikationsjahr

2015

Umfangsangabe

XIII, 211 S.

Sprache

Englisch

Beurteiler*innen

Guiseppe Francesco Italiano ,

Aleksander Madry

Klassifikationen

54 Informatik > 54.10 Theoretische Informatik ,

54 Informatik > 54.62 Datenstrukturen

AC Nummer

AC12374916

Utheses ID

33103

Studienkennzahl

UA | 786 | 880 | |

Detailansicht

Abstracts

Schlagwörter