Graph exploration with advice and online crossing minimization

Fuchs, Janosch; Unger, Walter (Thesis advisor); Komm, Dennis (Thesis advisor); Rossmanith, Peter (Thesis advisor)

Aachen : RWTH Aachen University (2022)
Doktorarbeit

Dissertation, RWTH Aachen University, 2022

Kurzfassung

Die Eingabe einer Instanz eines Online-Problems wird nur Stück für Stück aufgedeckt und erfordert jedes Mal eine unwiderrufliche Entscheidung, wenn ein neues Teilstück aufgedeckt wird. Dieses Szenario modelliert kritische Anwendungen bei denen eine Entscheidung, sobald sie einmal getroffen wurde, nicht mehr rückgängig gemacht werden kann und auch zukünftige Entscheidungen beeinflusst. Wie bei klassischen Offline-Problemen, ist es üblich eine worst-case Analyse zu machen um eine Garantie für die Leistung eines Online-Algorithmus zu erhalten. Für die Worst-Case-Analyse wird angenommen, dass ein böswilliger Gegenspieler, der das Verhalten des Online-Algorithmus kennt, die Eingabe erstellt. Online-Algorithmen schaffen es nur selten eine optimale Lösung zu bestimmen. Deshalb wird ihre Leistung mit der competitive ratio gemessen, die die Lösung des online Algorithmus mit der optimalen Lösung vergleicht, die erreicht werden kann, wenn die komplette Eingabe im Vorhinein bekannt ist. Um die Auswirkungen des fehlenden Wissens über die zukünftigen Anfragen zu messen, wurde das klassische Online-Szenario um ein hilfreiches Orakel erweitert, das Auskunft über die noch kommenden Eingabeteile gibt. Der Online-Algorithmus kann über ein Band auf die Information zugreifen. Dieses Band ist mit einer Sequenz von Bits beschriftet. Die Anzahl der während der Berechnung gelesenen Bits ist dann die so genannte advice complexity. Durch möglichst scharfe Schranken an die advice complexity eines Algorithmus, der ein Online-Problem optimal löst, zeigt man wie viele Informationen über die Zukunft wirklich notwendig sind, um alle Fehler zu vermeiden. Eine offensichtliche obere Schranke für die advice complexity eines jeden Online-Problems ist die Größe einer binären Codierung der kompletten Eingabe oder der kompletten optimalen Lösung. Aber meistens ist es möglich, bessere Schranken zu entwickeln indem man nur kritische Entscheidungen codiert, was den schweren Kern eines Problems offenbart. Daher besteht ein starker Zusammenhang zwischen der advice complexity und der Schwere eines Online-Problems. Somit ist es möglich, mit Hilfe der advice complexity die Komplexität verschiedener Online-Probleme miteinander zu vergleichen. Der erste technische Teil dieser Dissertation betrachtet ein Online-Graphzeichnungsproblem auf bipartiten Graphen mit beschränktem Grad. Das Problem wird online slotted One-Sided Crossing Minimzation genannt (online slotted OSCM-$k$). Eine der bipartiten Mengen von Knoten und eine dazugehörige Anordnung auf einer Geraden sind zu Beginn bekannt. In jedem Schritt muss ein Knoten, der mit $k$ Knoten aus der bereits bekannten Menge verbunden ist, einem leerem Platzhalter zugeordnet werden. Diese Platzhalter werden slots genannt und sind ebenfalls auf einer Linie angeordnet, die parallel zu der Linie verläuft auf der die bereits bekannten Knoten angeordnet sind. Die Aufgabe besteht darin, die Knoten so zu platzieren, dass die Anzahl der Kreuzungen zwischen den Kanten minimiert wird, wenn alle Kanten als gerade Linien gezeichnet werden. Die slots machen das Problem schwer für einen Online-Algorithmus, aber für die Betrachtung im Offline-Fall machen sie keinen Unterschied. Wir zeigen, dass die competitive ratio des online slotted OSCM-$k$ nicht durch eine konstante beschränkt ist und entwickeln obere und untere Schranken für das Problem, wenn die Eingabe auf $2$-reguläre Graphen beschränkt ist. Der zweite Teil analysiert die advice complexity eines Graph Exploration Problems. Bei diesem Problem muss ein Algorithmus einen Agenten über die Kanten eines Graphen von Knoten zu Knoten bewegen, sodass der Agent die günstigste oder kürzeste Tour abläuft, die alle Knoten des Graphen mindestens einmal besucht. Der Algorithmus kennt dabei den Graphen zu Beginn nicht, sieht aber jedes Mal, wenn der Agent auf einem neuen Knoten ist, die mit einer Kante erreichbare Nachbarschaft und die dazugehörigen Kosten der Kante. Bereits gesehene oder besuchte Knoten werden dabei wiedererkannt. Bedingt durch die bereits bekannte obere Schranke von $n\log(n)$, die asymptotisch identisch mit der unteren Schranke ist, konzentrieren wir uns auf Graphen, die im Verhältnis zu den Knoten nur linear viele Kanten haben. Wir zeigen, dass eine in der Anzahl der Kanten lineare Menge von Advice-Bits ausreicht und auch notwendig ist, um das graph exploration Problem auf gerichteten und ungerichteten Graphen zu lösen. Wir untersuchen zusätzlich noch, wie viel Advice eingespart werden kann, wenn die Struktur des Graphen (die Kanten und Knoten) im Vorhinein bekannt ist und nur die Information über die Kosten der Kanten fehlt.