Prioritní shoda - Priority matching

v teorie grafů, a prioritní shoda (také zvaný: maximální prioritní shoda) je vhodný který maximalizuje počet vrcholů s vysokou prioritou, které se účastní párování. Formálně dostáváme graf G = (PROTI, E) a oddíl sady vrcholů PROTI do některých k podmnožiny, PROTI1, ..., PROTIk, volala prioritní třídy. Prioritní shoda je shoda, která ze všech možných shod nasycuje největší počet vrcholů PROTI1; podle toho saturuje největší počet vrcholů od PROTI2; podle toho saturuje největší počet vrcholů od PROTI3; a tak dále.

Prioritní párování zavedlo Alvin Roth, Tayfun Sonmez a Utku Unver[1] v kontextu výměna ledvin. V tomto problému jsou vrcholy páry pacientů a dárců a každý okraj představuje vzájemnou lékařskou kompatibilitu. Například hrana mezi párem 1 a párem 2 naznačuje, že dárce 1 je kompatibilní s pacientem 2 a dárce 2 je kompatibilní s pacientem 1. Třídy priorit odpovídají lékařské prioritě mezi pacienty. Někteří pacienti jsou například ve vážnějším stavu, takže je třeba je nejdříve porovnat. Roth, Sonmez a Unver předpokládali, že každá prioritní třída obsahuje jeden vrchol, tj. Prioritní třídy indukují celková objednávka mezi páry.

Později Yasunori Okumura[2] rozšířil práci na prioritní třídy, které mohou obsahovat libovolný počet vrcholů. Ukázal také, jak efektivně najít prioritní shodu pomocí algoritmu pro shoda maximální mohutnosti, se složitostí běhu O (| V | | E | + | V |2 log | V |).

Jonathan S. Turner[3] představil variantu metody rozšiřující cestu (Edmondsův algoritmus ), který najde prioritní shodu v čase O (| V | | E |). Později našel rychlejší algoritmus pro bipartitní grafy: algoritmus běží v čase O (k | E | | V |1/2).[4]

Viz také

Reference

  1. ^ Roth, Alvin E .; Sönmez, Tayfun; Utku Ünver, M. (01.12.2005). „Párová výměna ledvin“. Journal of Economic Theory. 125 (2): 151–188. doi:10.1016 / j.jet.2005.04.004. ISSN  0022-0531. S2CID  583399.
  2. ^ Okumura, Yasunori (01.11.2014). „Prioritní shody byly znovu navštíveny“. Hry a ekonomické chování. 88: 242–249. doi:10.1016 / j.geb.2014.10.007. ISSN  0899-8256.
  3. ^ Turner, Jonathan (2015-12-28). "Maximium Priority Matchings". arXiv:1512.08555 [cs.DS ].
  4. ^ Turner, Jonathan (2015-12-31). "Rychlejší porovnávání priorit s maximem v bipartitních grafech". arXiv:1512.09349 [cs.DS ].