Les turotiels du GdR ROD :

Introduction to parameterized complexity

Valia Mitsou   IRIF, Université Paris Cité

Parameterized complexity is a branch of computational complexity that provides tools for tackling NP-hard problems. Rather than measuring complexity solely in terms of input size, parameterized complexity offers a more refined analysis in which the running time of an algorithm is expressed as a function of both the input size and one or more parameters. When these parameters are expected to be small, algorithms that are polynomial in the input size but exponential in the parameter(s) can still be considered tractable, since the exponential behavior is confined to the small parameter(s).

In this presentation, we will introduce the theory of parameterized complexity. We will survey the classical techniques used in the design of parameterized algorithms and then move on to structural parameterizations, focusing in particular on treewidth, one of the most successful and widely used structural parameters. Finally, we will discuss notions of parameterized hardness, including W-hardness and fine-grained complexity.

Ordonnancements multi acteurs

Fanny Pascual   LIP6, Sorbonne Université

Un problème d'ordonnancement consiste à organiser dans le temps l'exécution de tâches, en tenant compte de différentes contraintes (temporelles, de ressources,...), et en optimisant un ou plusieurs critères. Dans ce tutoriel, nous nous intéressons aux problèmes d’ordonnancement impliquant plusieurs personnes ou entités, que nous appellerons agents.  Il pourra s'agir du cas où les agents ont chacun leurs propres tâches qui doivent être exécutées sur des machines partagées ; du cas où les agents partagent tâches et machines ; et du cas où les tâches n'appartiennent pas à des agents en particulier, mais sont communes à tous les agents, chacun ayant ses préférences sur leur ordre d’exécution. 
Ces problématiques se situent à l’interface de plusieurs domaines : la théorie de l’ordonnancement, l’optimisation multicritère, la théorie des jeux algorithmique et le choix social computationnel. Ce tutoriel proposera un panorama des principaux modèles existants ainsi que des principales méthodes de résolution associées.

The perverse effects of turning scientific papers into accounting units

Cyril Labbé   LIG, Université Grenoble Alpes

Scientific Papers—and the citations accompanying them—were originally intended to disseminate knowledge. Increasingly, however, they are being treated as (ac)counting units for evaluation. Information systems that manage scientific publications can compute a wide range of metrics and rankings, which now shape the core logic of publishing activity. In this talk, we will see that this has led to new types of bizarre artifacts that can be automatically detected: meaningless publications, tortured phrases, irrelevant or sneaked references, etc.

Uncovering and analyzing these practices forms part of the ERC Synergy project NanoBubbles, dedicated to understanding “how, when, and why science fails to self-correct.” Within this project, several actions of research focus on the automatic analysis of scientific articles: detecting inappropriate citations; examining the impact of retracted papers on claims and reasoning in citing articles; detection of new tortured phrases and more.

Routing dans les entrepôts logistique : exploiter la configuration rectangulaire

Maxime Ogier   CRIStAL, Centrale Lille

Dans ce tutoriel, nous verrons comment exploiter la configuration rectangulaire des entrepôts logistiques pour développer des algorithmes de routing efficaces. La configuration rectangulaire signifie que l'espace de stockage est conçu avec un ensemble d'allées (verticales) parallèles dans lesquelles sont rangées les produits, ainsi qu'un ensemble d'allées (horizontales) perpendiculaires aux premières, qui permettent la navigation des préparateurs de commande. Nous nous focaliserons dans ce tutoriel sur les deux décisions principales qui doivent être prises dans la gestion des entrepôts logistiques : le regroupement des commandes et le routing des préparateurs de commande. Ces problèmes partagent des similarités avec les problèmes classiques de tournées de véhicules et du voyageur de commerce. Cependant, la configuration rectangulaire des entrepôts permet de proposer des méthodes de résolution efficaces. Typiquement, le problème de voyageur de commerce, appliqué dans un entrepôt avec deux allées horizontales, peut être résolu par un programme dynamique en temps polynomial. Nous verrons que ceci fournit un levier algorithmique intéressant pour résoudre des problèmes plus complexes dans les entrepôts.