Efficient graph exploration
| dc.contributor.advisor | Disser, Yann | |
| dc.contributor.advisor | Klimm, Max | |
| dc.contributor.author | Hackfeld, Jan | |
| dc.contributor.grantor | Technische Universität Berlin | en |
| dc.contributor.referee | Disser, Yann | |
| dc.contributor.referee | Klimm, Max | |
| dc.contributor.referee | Meyer auf der Heide, Friedhelm | |
| dc.contributor.referee | Skutella, Martin | |
| dc.date.accepted | 2018-10-12 | |
| dc.date.accessioned | 2019-09-26T09:50:48Z | |
| dc.date.available | 2019-09-26T09:50:48Z | |
| dc.date.issued | 2019 | |
| dc.description.abstract | The thesis “Efficient Graph Exploration” studies the following three closely related problems, where collaborating mobile agents move in a graph and have to jointly perform a certain task. Chapter 2 “Space Efficient Graph Exploration” considers the problem of deterministically exploring an undirected and initially unknown graph with n vertices either by a single agent equipped with a set of pebbles or by a set of collaborating agents. The goal is to understand how the memory requirement decreases compared to the case of single agent exploration as the agent may mark vertices by dropping and retrieving distinguishable pebbles, or when multiple agents jointly explore the graph. It is shown that for a single agent with constant memory θ(log log n) pebbles are both necessary and sufficient for exploring any undirected graph with n vertices. The second main result is that θ(log log n) agents with constant memory each are necessary and sufficient for the same task. Thus collaborating agents are not more powerful than pebbles in this setting. Chapter 3 “Energy Efficient Tree Exploration” considers a model where an agent consumes energy proportional to the number of edges it traverses and every agent has a fixed energy budget B bounding the number of edges it can traverse. All agents start at the root of a tree and have no initial knowledge about its structure. The objective is to maximize the number of distinct vertices collectively visited by the given agents compared to an algorithm that has complete knowledge of the tree in advance. A 3-competitive algorithm for the problem is presented together with a lower bound of 2.17 on the competitive ratio of any online algorithm. In Chapter 4 “Energy Efficient Delivery”, the agents also consume energy proportional to the distance they travel, but different agents can have different rates of energy consumption. The task of the agents is to deliver a set of messages, which are specified as source-target pairs in an undirected weighted graph, while minimizing the total energy consumption for this task. The aim is to investigate how the agents benefit from collaborating on delivering the messages compared to the case that every message is only transported by a single agent. It is shown how an optimal solution to the delivery problem can be 2-approximated by a solution, where messages are only transported by a single agent. It is further proved that this is best possible for arbitrary number of messages and agent capacity, i.e., number of messages that can be transported at the same time. | en |
| dc.description.abstract | In der Dissertation „Efficient Graph Exploration“ werden verschiedene Modelle untersucht, in denen sich kooperierende mobile Agenten in einem Graphen bewegen um zusammen eine Aufgabe zu erledigen. In Kapitel 2 „Space Efficient Graph Exploration“ wird analysiert, wie ein Agent mit sogenannten Pebbles oder mehrere kooperierende Agenten deterministisch einen ungerichteten und anfangs unbekannten Graphen mit The thesis “Efficient Graph Exploration” studies the following three closely related problems, where collaborating mobile agents move in a graph and have to jointly perform a certain task. Chapter 2 “Space Efficient Graph Exploration” considers the problem of deterministically exploring an undirected and initially unknown graph with n vertices either by a single agent equipped with a set of pebbles or by a set of collaborating agents. The goal is to understand how the memory requirement decreases compared to the case of single agent exploration as the agent may mark vertices by dropping and retrieving distinguishable pebbles, or when multiple agents jointly explore the graph. It is shown that for a single agent with constant memory θ(log log n) pebbles are both necessary and sufficient for exploring any undirected graph with n vertices. The second main result is that θ(log log n) agents with constant memory each are necessary and sufficient for the same task. Thus collaborating agents are not more powerful than pebbles in this setting. Chapter 3 “Energy Efficient Tree Exploration” considers a model where an agent consumes energy proportional to the number of edges it traverses and every agent has a fixed energy budget B bounding the number of edges it can traverse. All agents start at the root of a tree and have no initial knowledge about its structure. The objective is to maximize the number of distinct vertices collectively visited by the given agents compared to an algorithm that has complete knowledge of the tree in advance. A 3-competitive algorithm for the problem is presented together with a lower bound of 2.17 on the competitive ratio of any online algorithm. In Chapter 4 “Energy Efficient Delivery”, the agents also consume energy proportional to the distance they travel, but different agents can have different rates of energy consumption. The task of the agents is to deliver a set of messages, which are specified as source-target pairs in an undirected weighted graph, while minimizing the total energy consumption for this task. The aim is to investigate how the agents benefit from collaborating on delivering the messages compared to the case that every message is only transported by a single agent. It is shown how an optimal solution to the delivery problem can be 2-approximated by a solution, where messages are only transported by a single agent. It is further proved that this is best possible for arbitrary number of messages and agent capacity, i.e., number of messages that can be transported at the same time. n Knoten explorieren können. Es wird gezeigt, dass für einen Agenten mit konstanter Speichergröße θ(log log n) Pebbles hinreichend und notwendig sind, um jeden Graphen mit n Knoten zu explorieren. Es wird außerdem bewiesen, dass für die gleiche Aufgabe θ(log log n) Agenten mit konstanter Speichergröße hinreichend und notwendig sind. Das heißt, in diesem Modell sind zusätzliche kooperierende Agenten nicht mächtiger als zusätzliche Pebbles. In Kapitel 3 „Energy Efficient Tree Exploration“ wird ein Modell betrachtet, in dem ein Agent Energie proportional zur Anzahl der traversierten Kanten verbraucht. Jeder Agent besitzt ein festes Energiebudget B und kann daher höchstens B Kanten traversieren. Anfangs befinden sich alle Agenten an der Wurzel eines Baumes und haben keinerlei Wissen über dessen Struktur. Das Ziel ist eine maximale Anzahl an Knoten mit den Agenten zu besuchen im Vergleich zu einem Algorithmus, der den kompletten Baum von Anfang an kennt. Es wird ein 3-kompetitiver Algorithmus für das Problem vorgestellt, sowie eine untere Schranke für die Competitive Ratio von 2.17 gezeigt. In Kapitel 4 „Energy Efficient Delivery“ wird ebenfalls ein Modell betrachtet, in dem Agenten Energie proportional zur Distanz, die sie im Graphen zurücklegen, verbrauchen. Allerdings kann sich in diesem Modell die Effizienz der Agenten, das heißt, deren Verbrauchsrate, unterscheiden. Die Aufgabe der Agenten ist eine Menge an Nachrichten jeweils von verschiedenen Startknoten zu verschiedenen Zielknoten in einem ungerichteten gewichteten Graphen zu transportieren und dabei die Gesamtmenge an verbrauchter Energie zu minimieren. Der Fokus in diesem Kapitel ist zu untersuchen, wie die Agenten davon profitieren können, zusammen zu wirken um eine Nachricht ans Ziel zu transportieren gegenüber dem Fall, dass jede Nachricht nur durch einen Agenten transportiert wird. Es wird gezeigt, wie sich eine optimale Lösung für das Problem in eine Lösung mit höchstens 2-fachen Kosten transformieren lässt, in der jede Nachricht nur von einem Agenten transportiert wird. Es stellt sich heraus, dass dies im Allgemeinen bestmöglich ist. | de |
| dc.description.sponsorship | DFG, SPP 1736, Algorithmen für große Datenmengen | en |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/9671 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-8714 | |
| dc.language.iso | en | en |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | en |
| dc.subject.ddc | 510 Mathematik | de |
| dc.subject.other | graph exploration | en |
| dc.subject.other | online algorithm | en |
| dc.subject.other | competitive analysis | en |
| dc.subject.other | approximation algorithm | en |
| dc.subject.other | complexity theory | en |
| dc.subject.other | Graphexploration | de |
| dc.subject.other | Online-Algorithmus | de |
| dc.subject.other | kompetitive Analyse | de |
| dc.subject.other | Approximationsalgorithmus | de |
| dc.subject.other | Komplexitätstheorie | de |
| dc.title | Efficient graph exploration | en |
| dc.title.translated | Effiziente Graphexploration | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | acceptedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Diskrete Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.group | FG Diskrete Mathematik | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |