h1

000853316 001__ 853316
000853316 005__ 20251014090902.0
000853316 0247_ $$2HBZ$$aHT021491183
000853316 0247_ $$2Laufende Nummer$$a41559
000853316 0247_ $$2datacite_doi$$a10.18154/RWTH-2022-08761
000853316 037__ $$aRWTH-2022-08761
000853316 041__ $$aEnglish
000853316 082__ $$a004
000853316 1001_ $$0P:(DE-82)IDM00584$$aFuchs, Janosch$$b0$$urwth
000853316 245__ $$aGraph exploration with advice and online crossing minimization$$cvorgelegt von Janosch Fuchs, Master of Science$$honline
000853316 260__ $$aAachen$$bRWTH Aachen University$$c2022
000853316 300__ $$a1 Online-Ressource : Illustrationen
000853316 3367_ $$02$$2EndNote$$aThesis
000853316 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
000853316 3367_ $$2BibTeX$$aPHDTHESIS
000853316 3367_ $$2DRIVER$$adoctoralThesis
000853316 3367_ $$2DataCite$$aOutput Types/Dissertation
000853316 3367_ $$2ORCID$$aDISSERTATION
000853316 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University
000853316 502__ $$aDissertation, RWTH Aachen University, 2022$$bDissertation$$cRWTH Aachen University$$d2022$$gFak01$$o2022-08-26
000853316 5203_ $$aDie 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.$$lger
000853316 520__ $$aOnline problems reveal their input instance piece by piece and require an irrevocable decision each time a new piece is revealed. This scenario models critical applications where a decision, once it is made, cannot be changed afterwards which also influences future decisions. Like for classical offline problems, it is common to make a worst-case analysis to give a guarantee on the performance of algorithms in this setting, which are called online algorithms. This is achieved by assuming that a malicious adversary, knowing the behavior of the online algorithm, creates the input. Due to the nature of uncertainty online algorithms rarely compute an optimal solution. Thus, their performance is measured in terms of the competitive ratio, which compares the solution computed by the online algorithm to the optimal solution achievable when the whole instance is known beforehand. To measure the impact of the missing knowledge about the future the classical online setting was extended with a helpful oracle providing information about the future input. The online algorithm receives the information by accessing a tape containing a binary bit string prepared by the oracle. The number of bits that the algorithm reads during its computation is called its advice complexity. Bounds on the advice complexity of an online algorithm that optimally solves an online problem show how much information about the future is needed to avoid any mistake. An obvious upper bound for the advice complexity of all online problems is the size of the binary encoding of the input instance or the optimal solution using self-delimiting encoding. But most of the time it is possible to derive better bounds by encoding only critical decisions which then reveals the core difficulty of an online problem. Thus, the advice complexity strongly correlates to the difficulty of an online problem and it can be used to measure the difficulty of different online problems. The first technical part of this thesis considers an online graph drawing problem on degree-bounded bipartite graphs, the so-called online slotted One-Sided Crossing Minimization Problem (online slotted OSCM-$k$). One set of vertices together with a total ordering is fixed on a line and known to the online algorithm. In each step a vertex, which is incident to $k$ vertices of the already known set, needs to be placed on a free placeholder, which we call a slot. The slots are also arranged on a line parallel to the known vertex set. The task is to place the vertices such that the number of edge crossings is minimized, when all edges are drawn as straight lines. Note that the slots make the problem harder to solve for an online algorithm but in the offline case it is equivalent to the version without slots. We prove that the online slotted OSCM-$k$ has no constant competitive ratio. Thus, we look at the problem on $2$-regular graphs and derive constant upper and lower bounds for this restricted graph class. The second part analyzes the advice complexity of a graph exploration problem. Here, an algorithm has to move an agent through a graph from vertex to vertex using the edges such that the agent traverses the cheapest or shortest tour that visits every vertex at least once. The algorithm does not know the graph beforehand and each time the agent is located at a new vertex the reachable neighborhood is revealed together with the cost to reach all neighboring vertices from the current location. Already seen or visited vertices are recognizable. Due to the already known tight upper bound of $n\log(n)$ for the advice complexity of the graph exploration problem on dense graphs, we focus on sparse graphs. We show that the number of advice bits which is sufficient and also necessary to solve the graph exploration problem on directed and undirected graphs is linear in the number of edges. We also investigate how much advice can be saved when the graph structure is known beforehand and only the traveling cost of the edges is unknown.$$leng
000853316 588__ $$aDataset connected to Lobid/HBZ
000853316 591__ $$aGermany
000853316 653_7 $$aadvice complexity
000853316 653_7 $$acrossing minimization
000853316 653_7 $$agraph exploration
000853316 653_7 $$aonline algorithms
000853316 7001_ $$0P:(DE-82)IDM04394$$aUnger, Walter$$b1$$eThesis advisor$$urwth
000853316 7001_ $$0P:(DE-82)115030$$aKomm, Dennis$$b2$$eThesis advisor
000853316 7001_ $$0P:(DE-82)IDM00088$$aRossmanith, Peter$$b3$$eThesis advisor$$urwth
000853316 8564_ $$uhttps://publications.rwth-aachen.de/record/853316/files/853316.pdf$$yOpenAccess
000853316 8564_ $$uhttps://publications.rwth-aachen.de/record/853316/files/853316_source.zip$$yRestricted
000853316 909CO $$ooai:publications.rwth-aachen.de:853316$$pdnbdelivery$$pdriver$$pVDB$$popen_access$$popenaire
000853316 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00584$$aRWTH Aachen$$b0$$kRWTH
000853316 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM04394$$aRWTH Aachen$$b1$$kRWTH
000853316 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00088$$aRWTH Aachen$$b3$$kRWTH
000853316 9141_ $$y2022
000853316 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000853316 9201_ $$0I:(DE-82)121110_20140620$$k121110$$lLehrstuhl für Informatik 1 (Algorithmen und Komplexität)$$x0
000853316 9201_ $$0I:(DE-82)120000_20140620$$k120000$$lFachgruppe Informatik$$x1
000853316 9201_ $$0I:(DE-82)080060_20170720$$k080060$$lGraduiertenkolleg UnRAVeL$$x2
000853316 961__ $$c2022-10-04T10:04:54.669304$$x2022-09-07T20:09:55.311049$$z2022-10-04T10:04:54.669304
000853316 9801_ $$aFullTexts
000853316 980__ $$aI:(DE-82)120000_20140620
000853316 980__ $$aI:(DE-82)121110_20140620
000853316 980__ $$aUNRESTRICTED
000853316 980__ $$aVDB
000853316 980__ $$aphd
000853316 980__ $$aI:(DE-82)080060_20170720