Time table of all LIRMM seminars

Matching markets have diverse applications, ranging from kidney transplantation to internship assignments. This talk focuses on many-to-one stable matching in the context of school choice. These are two-sided markets comprising students (children) and schools, which hold preferences and priorities, respectively, over one another. We begin by exploring classic game theory concepts that underpin these market-matching mechanisms. Motivated by the Chilean school choice system, we use integer programming to model mechanisms that not only determine matchings between students and schools but also allocate additional seats to schools to optimize student welfare.

As the space sector undergoes rapid expansion with projects like Starlink, satellite IoT networks, and the NASA-ESA-JAXA LunaNet system, space networking faces critical computer science challenges. This seminar will explore key research areas where computational techniques are shaping the future of space communications. Mega-constellations require scalable routing, scheduling, and traffic management solutions to handle latency and network dynamics. Direct-to-satellite access for smartphones and IoT devices demands novel energy-efficient protocols and seamless space-terrestrial integration. The vision of a Solar System Internet introduces fundamental issues in delay-tolerant networking, scalability, and congestion control. Addressing these challenges requires advanced computational methodologies, including optimization, decision processes, and AI-driven techniques, to enable reliable and efficient global and interplanetary connectivity.

This talk presents the combinatorics of permutations and patterns as a special case of ordered graphs.
After some fundamental definitions and examples, I will introduce a key theorem of Marcus and Tardos on the density of pattern-avoiding matrices, and explain how it lead Guillemot and Marx to design a fixed parameter tractable algorithm to find patterns in permutations, through the introduction of what is now known as twin-width. I will conclude by presenting a recent result on the interaction between patterns and composition of permutations.

Based on joint work with Édouard Bonnet, Romain Bourneuf, and Stéphan Thomassé

On classe parfois les langages de programmation en deux grandes catégories : les langages statiques, tels que C, Rust et OCaml, et les langages dynamiques, tels que Python, JavaScript et Elixir. Si les langages statiques offrent généralement de meilleures performances et une plus grande sûreté grâce à une phase de typage statique qui précède la compilation (« well-typed programs cannot go wrong »), cela se fait souvent au détriment de la flexibilité, rendant les programmes plus sûrs mais le prototypage plus fastidieux. Dans cet exposé, je présente un système de type statique adapté aux langages dynamiques, offrant ainsi un compromis entre sûreté et flexibilité.

Le typage statique de langages dynamiques pose de nombreux défis. En particulier, les fonctions peuvent être surchargées : elles peuvent exhiber des comportements différents selon le type de leurs paramètres. La sélection (dispatch) parmi ces différents comportements ne peut pas toujours être faite statiquement, et a généralement lieu au moment de l’exécution (soit via des tests de type explicites, soit via un mécanisme de dispatch dynamique intégré au langage). En outre, les programmes n’ont généralement pas (ou peu) d’annotations de type. Pour résoudre ces problèmes, je présente un système de types qui combine, de manière contrôlée, du polymorphisme de premier ordre, des types intersection, des types union et du sous-typage, et fournit un algorithme pour déduire automatiquement le type des fonctions (inférence de type). Il en résulte une discipline de type dans laquelle des fonctions non annotées reçoivent des types polymorphes (grâce à Hindley-Milner) qui peuvent capturer le comportement surchargé des fonctions qu’ils typent (grâce aux types intersection) et qui sont déduits en appliquant des techniques avancées de rétrécissement de type (grâce aux types union).

A {\em replacement action} is a function $\cal L$ that maps each graph to a collection of subgraphs of smaller size.

Given a graph class $\cal H$, we consider a general family of graph modification problems, called {\sc $\cal L$-Replacement to $\cal H$}, where the input is a graph $G$ and the question is whether it is possible to replace some induced subgraph $H_1$ of $G$ on at most $k$ vertices by a graph $H_2$ in ${\cal L}(H_1)$ so that the resulting graph belongs to $\cal H$.

{\sc $\cal L$-Replacement to $\cal H$} can simulate many graph modification problems including vertex deletion, edge deletion/addition/edition/contraction, vertex identification, subgraph complementation, independent set deletion, (induced) matching deletion/contraction, etc.

We prove here that, for any minor-closed graph class $\cal H$ and for any action $\cal L$ that is hereditary, there is an algorithm that solves {\sc $\cal L$-Replacement to $\cal H$} in time $2^{{\sf poly}(k)}\cdot |V(G)|^2$, where ${\sf poly}$ is a polynomial whose degree depends on $\cal H$.

Sustainable agriculture plays a fundamental role in ensuring long-term food security and environmental stability, addressing challenges such as resource depletion, biodiversity loss, and climate change. However, these sustainability requirements introduce additional complexities in crop planning, making it increasingly difficult for farmers to optimize land use while complying with environmental regulations and managing climate variability.

To support farmers in maximizing their long-term revenues, a multi-period Crop Rotation Planning (CRP) model is presented, that incorporates sustainability constraints. The problem is first formulated as an Integer Linear Programming (ILP) model. As an improvement, a network-based ILP formulation using an arc-flow representation is introduced, which provides a stronger formulation by efficiently capturing the structure of crop rotations over multiple seasons. Since exact methods become computationally intractable for large-scale instances, we further develop a matheuristic approach based on column generation, where the pricing subproblem is analyzed from a complexity-theoretic perspective. Additionally, we present a complexity analysis of the pricing problem and an optimal dynamic programming algorithm for a special case. To validate our approach, we conduct an extensive computational study using real-world data from Italian farms, integrating sustainability constraints derived from the Common Agricultural Policy (CAP) of the European Union. Furthermore, our model serves as a policy analysis tool, enabling the assessment of the economic impact of new sustainability policies on both farmers and the agricultural sector.