Appariements, polytopes et dons d'organes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Appariements, polytopes et dons d'organes

Résumé

Les programmes de dons croisés de reins donnent lieu à un problème d'appariement complexe pour lequel une solution optimale est inconnue. Ce problème peut être décrit par un modèle d'appariement dynamique et aléatoire où des éléments de différentes classes arrivent selon des processus de Poisson indépendants. Chaque élément représente un couple donneur-receveur où le donneur, prêt à donner un rein pour le receveur, est incompatible avec lui ; et la classe encode des propriétés du couple, telles que les groupes sanguins du donneur et du receveur, qui influencent sa compatibilité. Les contraintes d'appariement sont décrites par un graphe non-orienté dont les sommets sont les classes : deux couples ont des classes voisines dans le graphe s'ils peuvent être appariés dans le sens où chaque donneur peut donner son rein au receveur de l'autre couple. Les éléments en attente sont stockés dans une file d'attente. Nous étudions l'efficacité des politiques d'appariement, non seulement en termes de stabilité du système, mais aussi de contrôle des taux d'appariement entre différentes classes. Ce dernier point est important en vue de privilégier les appariements maximisant d'autres mesures de performance, comme la qualité de vie après la transplantation ou le taux de survie du greffon. Cet article présente les principales contributions sur les appariements dynamiques pré-publiés et implantés par les auteurs [CMB22, Mat]. Par souci de concision, les preuves sont omises dans la présente version. La partie 1 formalise le problème et introduit l'équation de conservation qui caractérise les taux d'appariement de toute politique stable. La partie 2 présente une relation simple reliant la structure du graphe, l'équation de conservation, et la stabilité du système. Cette relation nous permet de caractériser dans la partie 3 l'ensemble des solutions de l'équation de conservation comme un polytope convexe. Finalement, la partie 4 montre que tout point du polytope est atteignable ou approchable par des politiques simples qui éliminent certaines arêtes.
Fichier principal
Vignette du fichier
papier_clean.pdf (167.76 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03656130 , version 1 (01-05-2022)

Identifiants

  • HAL Id : hal-03656130 , version 1

Citer

Céline Comte, Fabien Mathieu, Ana Bušić. Appariements, polytopes et dons d'organes. AlgoTel 2022 - 24èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2022, Saint-Rémy-Lès-Chevreuse, France. ⟨hal-03656130⟩
65 Consultations
40 Téléchargements

Partager

Gmail Facebook X LinkedIn More