32 research outputs found
Effiziente Graphexploration
No full textThe 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.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.DFG, SPP 1736, Algorithmen für große Datenmenge
Undirected Graph Exploration with ⊝(log log n ) Pebbles
No full textWe consider the fundamental problem of exploring an undirected and initially unknown graph by an agent with little memory. The vertices of the graph are unlabeled, and the edges incident to a vertex have locally distinct labels. In this setting, it is known that Θ(logn) bits of memory are necessary and sufficient to explore any graph with at most n vertices. We show that this memory requirement can be decreased significantly by making a part of the memory distributable in the form of pebbles. A pebble is a device that can be dropped to mark a vertex and can be collected when the agent returns to the vertex. We show that for an agent O(log log n) distinguishable pebbles and bits of memory are sufficient to explore any bounded-degree graph with at most n vertices. We match this result with a lower bound exhibiting that for any agent with sub-logarithmic memory, Ω(log log n) distinguishable pebbles are necessary for exploration
Undirected Graph Exploration with Θ(log log n) Pebbles
No full textWe consider the fundamental problem of exploring an undi-rected and initially unknown graph by an agent with lit-tle memory. The vertices of the graph are unlabeled, and the edges incident to a vertex have locally distinct labels. In this setting, it is known that Θ(logn) bits of memory are necessary and sufficient to explore any graph with at most n vertices. We show that this memory requirement can be decreased significantly by making a part of the mem-ory distributable in the form of pebbles. A pebble is a device that can be dropped to mark a vertex and can be collected when the agent returns to the vertex. We show that for an agent O(log logn) distinguishable pebbles and bits of mem-ory are sufficient to explore any bounded-degree graph with at most n vertices. We match this result with a lower bound exhibiting that for any agent with sub-logarithmic memory, Ω(log logn) distinguishable pebbles are necessary for exploration
Comment explorer un arbre inconnu avec des agents à énergie limitée ?
No full textInternational audienceWe wish to explore an unknown tree with a team of k >= 1 initially collocated mobile agents. Each agent has limited energy and cannot,as a result, traverse more than B edges. The goal is to maximize the number of nodes collectively visited by all agents during the execution.Initially, the agents have no knowledge about the structure of the tree,but they gradually discover the topology as they traverse new edges. We assume that the agents can communicate with each other at arbitrary distances, therefore the knowledge obtained by one agent after traversing an edge is instantaneously transmitted to the other agents.We propose an intuitive algorithm based on depth-first search and westudy its performance compared to the optimal solution that we could obtain if we knew in advance the map of the tree. We prove that this algorithm has a constant competitive ratio. We also provide a lower bound on the competitive ratio of any algorithm.On souhaite explorer un arbre inconnu avec une équipe de k \geq 1 agents mobiles initialement regroupés sur un sommet. Chaque agent dispose d'une énergie limitée et ne peut pas traverser plus de B arêtes. On souhaite maximiser le nombre de sommets visités par l'équipe d'agents lors de l'exécution. Initialement, les agents n'ont aucune connaissance sur la structure de l'arbre, mais ils en découvrent la topologie au fur et à mesure qu’ils traversent de nouvelles arêtes. Nous supposons que les agents peuvent communiquer entre eux à distance illimitée, donc la connaissance qu'un agent obtient lors de la traversée d'une arête est instantanément transmise aux autres agents. Nous proposons un algorithme très intuitif, basé sur le parcours en profondeur, et nous étudions son efficacité par rapport à la solution optimale qu'on peut obtenir lorsqu'on connaît initialement la carte. Nous prouvons que cet algorithme a un rapport de compétitivité constant. Nous fournissons également une borne inférieure sur le rapport de compétitivité réalisable par un algorithme quelconque
Energy-Efficient Delivery by Heterogeneous Mobile Agents
No full textWe consider the problem of delivering m messages between specified source-target pairs in an undirected graph, by k mobile agents initially located at distinct nodes of the graph. Each edge has a designated length and each agent consumes energy proportional to the distance it travels in the graph. We are interested in optimizing the total energy consumption for the team of agents. Unlike previous related work, we consider heterogeneous agents with different rates of energy consumption (weights w_i). To solve the delivery problem, agents face three major challenges: Collaboration (how to work together on each message), Planning (which route to take) and Coordination (how to assign agents to messages).
We first show that the delivery problem can be 2-approximated without collaborating and that this is best possible, i.e., we show that the benefit of collaboration is 2 in general. We also show that the benefit of collaboration for a single message is 1 / log 2 which is approximately 1.44. Planning turns out to be NP-hard to approximate even for a single agent, but can be 2-approximated in polynomial time if agents have unit capacities and do not collaborate. We further show that coordination is NP-hard even for agents with unit capacity, but can be efficiently solved exactly if they additionally have uniform weights. Finally, we give a polynomial-time c-approximation for message delivery with unit capacities
Tight Bounds for Online TSP on the Line
No full textInternational audienceWe consider the online traveling salesperson problem (TSP), where requests appear online over time on the real line and need to be visited by a server initially located at the origin. We distinguish between closed and open online TSP, depending on whether the server eventually needs to return to the origin or not. While online TSP on the line is a very natural online problem that was introduced more than two decades ago, no tight competitive analysis was known to date. We settle this problem by providing tight bounds on the competitive ratios for both the closed and the open variant of the problem. In particular, for closed online TSP, we provide a 1.64-competitive algorithm, thus matching a known lower bound. For open online TSP, we give a new upper bound as well as a matching lower bound that establish the remarkable competitive ratio of 2.04. Additionally, we consider the online Dial-A-Ride problem on the line, where each request needs to be transported to a specified destination. We provide an improved non-preemptive lower bound of 1.75 for this setting, as well as an improved preemptive algorithm with competitive ratio 2.41. Finally, we generalize known and give new complexity results for the underlying offline problems. In particular, we give an algorithm with running time for closed offline TSP on the line with release dates and show that both variants of offline Dial-A-Ride on the line are NP-hard for any capacity of the server
Tight bounds for online TSP on the line
No full textWe consider the online traveling salesperson problem (TSP), where requests appear online over time on the real line and need to be visited by a server initially located at the origin. We distinguish between closed and open online TSP, depending on whether the server eventually needs to return to the origin or not. While online TSP on the line is a very natural online problem that was introduced more than two decades ago, no tight competitive analysis was known to date. We settle this problem by providing tight bounds on the competitive ratios for both the closed and the open variant of the problem. In particular, for closed online TSP, we provide a 1.64-competitive algorithm, thus matching a known lower bound. For open online TSP, we give a new upper bound as well as a matching lower bound that establish the remarkable competitive ratio of 2.04. Additionally, we consider the online DIAL-A-RIDE problem on the line, where each request needs to be transported to a specified destination. We provide an improved non-preemptive lower bound of 1.75 for this setting, as well as an improved preemptive algorithm with competitive ratio 2.41. Finally, we generalize known and give new complexity results for the underlying offline problems. In particular, we give an algorithm with running time O(n) for closed offline TSP on the line with release dates and show that both variants of offline DIAL-A-RIDE on the line are NP-hard for any capacity c≥ 2 of the server
Prospects for -ray observations of the Perseus galaxy cluster with the Cherenkov Telescope Array
No full textGalaxy clusters are expected to be dark matter (DM) reservoirs and storage rooms for the cosmic-ray protons (CRp) that accumulate along the cluster\u27s formation history. Accordingly, they are excellent targets to search for signals of DM annihilation and decay at gamma-ray energies and are predicted to be sources of large-scale gamma-ray emission due to hadronic interactions in the intracluster medium. We estimate the sensitivity of the Cherenkov Telescope Array (CTA) to detect diffuse gamma-ray emission from the Perseus galaxy cluster. We perform a detailed spatial and spectral modelling of the expected signal for the DM and the CRp components. For each, we compute the expected CTA sensitivity. The observing strategy of Perseus is also discussed. In the absence of a diffuse signal (non-detection), CTA should constrain the CRp to thermal energy ratio within the radius down to about s for DM masses above 1 TeV. These constraints will provide unprecedented sensitivity to the physics of both CRp acceleration and transport at cluster scale and to TeV DM particle models, especially in the decay scenario.93 pages (including author list, appendix and references), 143 figures. Submitted to JCA
