Les problèmes d'appariement sont très classiques en théorie des graphes et consistent à sélectionner un sous-ensemble d'arêtes disjointes, dont on veut maximiser la cardinalité ou le poids cumulé des arêtes dans le cas d'un graphe pondéré.

Une variante intéressante de ce problème sur les graphes pondérés consiste à supposer que les poids ne sont pas connus à l'avance mais doivent être requêtés/calculés, opération que l'on suppose coûteuse.

Nous avons donc deux critères d'optimisation:
- le poids total de l'appariement que l'on souhaite maximiser
- le nombre de requêtes de calcul de poids que l'on souhaite minimiser

Dans un travail préliminaire, Romaric Duvignau (Chalmers University of Technology, Gothenburg, Suède) et Ralf Klasing (LaBRI, Bordeaux) ont proposés plusieurs algorithmes gloutons pour résoudre ce problème, offrant des garanties/compromis intéressant.e.s si on fait certaines hypothèses sur les poids des arêtes. Nous avons étendu ces travaux en proposant de nouvelles solutions, toujours gloutonnes.

Je me propose de vous présenter ces différentes solutions. Si le temps le permet, je présenterai également de nos pistes d'exploration actuelles sur des modèles dynamiques, où le graphe ne peut pas tenir en mémoire et où les arêtes doivent être traitées en flux (modèle semi- streaming).