Spelling suggestions: "subject:"couplage maximum"" "subject:"àcouplage maximum""
1 |
Quelques conséquences de la convergence locale faible pour les graphes aléatoiresSalez, Justin 04 July 2011 (has links) (PDF)
Dans la limite "diluée" où les nombres d'arêtes et de sommets divergent de manière comparable, il est naturel d'espérer que divers invariants classiques en théorie des graphes seront essentiellement déterminés par la seule "géométrie locale" du graphe -- c'est à dire, informellement, par l'aspect d'une boule de petit rayon autour d'un "sommet typique". Cette heuristique a pour origine l'étude des systèmes de particules en physique statistique, où sous certaines conditions, les contributions microscopiques provenant de sites suffisamment éloignés peuvent être considérées comme mutuellement indépendantes dans le calcul des grandeurs macroscopiques fondamentales du système. Mathématiquement, cette précieuse absence d'intéractions à longue portée peut se décrire rigoureusement à l'aide d'une propriété topologique : la continuité de l'invariant considéré vis-à-vis de la convergence locale faible des graphes. Tout invariant pour lequel on peut établir une telle continuité admettra aussitôt une limite déterministe le long de la plupart des suites de graphes aléatoires classiques, et pourra être efficacement approximé par des algorithmes locaux et distribués, indépendamment de la taille totale du système. Dans cette thèse, nous établissons la continuité de quatre invariants de graphes qui jouent un rôle essentiel en théorie comme dans les applications : la distribution spectrale empirique, la dimension du noyau de la matrice d'adjacence, la taille d'un couplage maximum, et le polynôme énumérant certaines familles de sous-graphes couvrants. Plus précisément, nous montrons qu'il existe une unique manière localement cohérente d'étendre chacune de ces notions aux limites locales faibles de graphes finis, et que ce prolongement est continu. Pour les modèles de graphes aléatoires classiques, les équations de cohérence locale se simplifient en une équation aux distributions que nous résolvons explicitement. Cela conduit à de nouvelles formules asymptotiques, ainsi qu'à la simplification, l'unification et la généralisation de divers résultats jusqu'alors isolés.
|
2 |
Weak core solution for the non-transferable utility kidney exchange gameCollette, Raphaël 08 1900 (has links)
Plusieurs pays possèdent des programmes de don croisé de rein (PDCR). Le but de ces
programmes est d’aider les patients ayant un donneur incompatible à obtenir une greffe, en
échangeant les donneurs incompatibles entre les patients. Pour pouvoir obtenir des bassins
de paires incompatibles de plus grande taille, il est possible d’élargir les PDCR pour y inclure
plusieurs pays ou hôpitaux. Par contre, on doit s’attendre à ce que ces derniers agissent de
façon stratégique pour maximiser le nombre de leurs patients obtenant une greffe. Avec ce
cadre, on peut définir le problème de don croisé de rein à plusieurs agents.
Dans ce mémoire, nous modélisons ce problème comme un jeu coopératif à utilité non-
transférable et nous présentons le noyau faible comme solution à ce jeu. Nous étudions
empiriquement notre solution sur des exemples basés sur des données réelles et montrons
qu’elle est atteignable en pratique. Nous comparons aussi le noyau faible à une autre solution
présente dans la littérature: les couplages résistants aux rejets. / In various countries, kidney paired donation programs (KPDs) are implemented. These
programs aim to help patients with an incompatible donor to obtain a transplant by swapping
the donors between the patients. In order to increase the size of the pool of incompatible
patient-donor pairs and potentially enhance patient benefits, KPDs can be extended to
include multiple countries or hospitals. However, unlike existing nationwide KPDs, strategic
behaviour from these entities (agents) is to be expected. This gives rise to the multi-agent
kidney exchange problem.
In this work, we model for the first time this problem as a non-transferable utility game.
We also propose and argue in favour of the use of the weak core as a solution concept for
the game. Using integer programming tools, we empirically study our solution concept on
instances from the literature, which are derived from real-world data, and show that it is
attainable in practice. We also compare the weak core to another recently presented solution
concept from the literature, the rejection-proof matching.
|
Page generated in 0.0472 seconds