Agenda
June
-
14:0015:00EnglishLaBRI
-
11:0012:00
Émile Naquin (LaBRI)
Title: Graph Exploration with Edge Weight Estimates
Abstract:
In the Travelling Salesman Problem, every vertex of an edge-weighted graph has to be visited by an agent who traverses the edges of the graph. In this problem, it is usually assumed that the costs of each edge are given in advance, making it computationally hard but possible to calculate an optimal tour for the agent.
Also in the Graph Exploration Problem, every vertex of a given graph must be visited, but here the graph is not known in the beginning - at every point, an algorithm only knows about the already visited vertices and their neighbors.
Both however are not necessarily realistic settings: Usually the structure of the graph (for example underlying road network) is known in advance, but the details are not. One usually has a prediction of how long it takes to traverse through a particular road, but due to road conditions or imprecise maps the agent might realize that a road will take slightly longer than expected when arriving on it. To deal with those deviations, it is natural to assume that the agent is able to adapt to the situation: When realizing that taking a particular road is more expensive than expected, recalculating the tour and taking another road instead is possible.
In a sense, this setting lies in between the offline travelling salesman problem, and the online problem of graph exploration, as it allows some computation at the beginning, but remains an online problem during traversal through the graph.
We analyze the competitive ratio of this problem based on the pertur- bation factor α of the edge weights. For general graphs we show that for realistic factors smaller than 2 there is no strategy that achieves a competitive ratio better than α, which can be matched by a simple algorithm.
In addition, we prove an algorithm which has a competitive ratio of (1+α)/2 for restricted graph classes like complete graphs with uniform announced edge weights. Here, we present a matching lower bound as well, proving that the strategy for those graph classes is best possible. We conclude with a remark about special graph classes like cycles.
EnglishLaBRI 178 -
16:0018:00
The jury consists of the following members:
Tamara Munzner
Raimund Dachselt
Niklas Elmqvist
Caroline Appert
David Auber
Amphi LaBRI -
09:3012:00
Aymeric Ferron will defend his thesis titled: “Exploring Concrete and Immersive Visualizations to Communicate the Environmental Impact of Everyday Actions.”
Salle Ada Lovelace (Inria)
July
-
14:0018:00
Nina Lassalle-Astis will defend her dissertation titled: “Development of a Hybrid Data Augmentation Methodology: Application to Supervised Defect Detection in X-ray Tomography.”
Amphi LaBRI