Agenda

Département
Langue
Date
Thématique
2026

June

  • 11:00
    12: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.

    https://algodist.labri.fr/index.php/Main/GT

    English
    LaBRI 178
  • 16:00
    18:00

    The jury consists of the following members:

    Tamara Munzner
    Raimund Dachselt
    Niklas Elmqvist
    Caroline Appert
    David Auber

    This habilitation explores the visualization of data in and about physical spaces. While there are myriad ways to approach this, this work focuses on a targeted subset, structured top-down: It starts with conceptual contributions which provide the backbone for tools and studies.

    The first part introduces three conceptual models and frameworks for visualizing data and making it experienceable in space: data physicalization, situated and embedded data representations and finally progressive value reading.

    The second part presents four tools and techniques which visualize data in or about spaces. First it discusses a method to analyze and compare tools to capture activities in fabrication workshops; a participatory data physicalization enabling people to capture multi-dimensional data about daily activities in or related to a space; finally two explorations of virtual representations of physical spaces: one putting uncertainty in physical trips on maps, and another using a simulated mini-world to illustrate the concept of sustainability.

    The third part summarizes three controlled experiments investigating different relationships of people with space: a conceptual replication study testing a presumed link between body posture and risky behaviors in a human-computer interaction context; a study on how visualization may augment debiasing approaches for spatial and temporal task estimates; and an exploration how concrete augmented reality visualizations in physical spaces may affect message credibility of visualizations.

    The habilitation concludes with reflections on methodological rigor, research transparency, and future research directions.

     

    It is also possible to follow the defense on zoom.

    Amphi LaBRI
  • 14:00
    17:00

    In this thesis, we focus on distributed algorithms of the LOCAL model that run in constant time—that is, whose number of rounds is independent of the number of vertices—applied to the approximation of dominance problems within various classes of graphs. We provide MDS approximation algorithms for parameterized graph families, where the approximation factor does not depend on the parameter. First, we prove that given a LOCAL algorithm that produces a good approximation on planar graphs, it can be transformed into a LOCAL algorithm that produces a good approximation on graphs embeddable in a surface of Eulerian genus. Building on the algorithm of Heydt et al., we derive an approximation with a factor of 34+E for graphs of bounded genus. This result significantly improves upon the previous state of the art of 24g+O(1) established by Ami ri et al., as well as the factor of 91 H: obtained by Czygrinow et al. in the special case of orientable surfaces. 
    We then generalize this result in two directions: first, by considering other graph problems studied in distributed computing, and second, by extending our results to classes of graphs beyond the bounded genus. We prove these results via a series of metatheorems concerning certain minimization problems. Next, we show that certain structured graphs (which exclude an H-minor with pathwidth at most 2) admit a deterministic distributed algorithm in f(H) rounds that computes a 50-approximation for the MDS problem. Although fast, approximate distributed algorithms for these problems were already known for graphs without minor H, all had an approximation factor dependent on H. A new key ingredient in the analysis of these various distributed algorithms is the use of the asymptotic dimension, a geometric concept introduced by Gromov in 1993. 

    Amphi LaBRI
  • 14:00
    17:00

    In computer science, graphs are one of the most common data structures used to store information. This thesis presents research on graphs designed to store other graphs as efficiently as possible. More specifically, we study different families of graphs and, for each one, we seek graphs capable of containing all those in the family while preserving their metric structure. Such graphs are called isometric universal graphs, and this thesis aims to find the smallest among them. By “smallest,” we mean those that require the least storage space. We first explore the structural and algorithmic properties of isometric universal graphs. Next, we highlight their connections to a related research area, that of distance labeling schemes. These are data structures that encode graphs while preserving their metric structure; however, unlike isometric universal graphs, these schemes are not themselves graphs. We then turn our attention to specific families of graphs. For these families, we seek to construct isometric universal graphs of the smallest size that is mathematically possible. This involves establishing lower bounds on the size of such graphs, bounds that are inherent to their structures. We are particularly interested in families of graphs with simple structures, such as trees, forests, or general graphs. Finally, we study algorithmic questions related to isometric universal graphs for these families and prove certain NP-completeness results. 

  • 10:00
    13:30

    Shared micromobility systems have become an essential part of urban transportation, offering flexible and sustainable solutions for short-distance travel. However, their large-scale deployment poses several operational challenges, including disorganized parking in free-floating systems, imbalances between supply and demand, high fleet management costs, increased safety risks, and limited integration with public transit. This thesis explores how artificial intelligence techniques can address these challenges by proposing data-driven approaches to improve the efficiency and safety of shared micromobility systems. First, the problem of disorganized parking in free-floating systems is addressed using a multi-layer clustering approach, which identifies high-demand areas and guides the placement of virtual stations. These dedicated spaces, deployed without physical infrastructure, help reduce improper parking and improve spatial organization.
    To ensure the system operates efficiently, a demand forecasting approach is proposed to address the imbalance between supply and demand. It estimates vehicle demand by location and time period, thereby facilitating fleet redistribution operations. This approach is also designed to be adaptable to other configurations, including systems with physical stations and free-floating systems.
    To ensure scalability while reducing communication overhead and latency, an edge-based architecture is introduced, enabling decentralized data processing and faster decision-making. Building on these contributions, operational decisions are optimized in real time using deep reinforcement learning. A first framework is dedicated to fleet management, recommending nearby alternative drop-off zones and involving users in the redistribution process. It integrates predicted demand and vehicle battery levels to maintain vehicle availability while reducing operational costs, limiting manual redistribution operations, and facilitating the aggregation of vehicles with low battery levels. A second framework addresses safety by recommending safer drop-off zones, based on urban factors such as traffic conditions, the presence of bike lanes, intersection density, lighting, and congestion. Finally, to improve first- and last-mile accessibility, this thesis extends the demand prediction framework to intermodal contexts, with the aim of improving vehicle availability in areas connected to public transportation.
    It combines local demand for public transportation with spatial and contextual factors that influence travel patterns. A hybrid graph-based deep learning framework is proposed to model these relationships and better represent urban mobility dynamics.
    All data inputs are integrated into an end-to-end intelligent management system, enabling real-time, user-centered decision-making. Experiments conducted on real-world urban case studies demonstrate the system’s effectiveness, including the accurate identification of virtual stations, reliable demand forecasting, and improved vehicle allocation through the recommendation of drop-off zones. Overall, this work contributes to the development of more efficient, safer, and more sustainable shared micromobility systems, and provides valuable insights for researchers and urban planners seeking to improve mobility services.

    Amphi LaBRI
  • 09:30
    12: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