Studentka se seznámí s problémem výměny ledviny a s existujícími heuristikami pro hledání stabilních permutací s krátkými cykly. Dále se pokusí navrhnout a implementovat vlastní vylepšení těchto heuristik, především z hlediska časové složitosti a praktické použitelnosti i pro velká vstupní data.
Seznam odborné literatury
K. Cechlárová, J. Hajduková: Stability testing in coalition formation games, Proc. SOR'99, Preddvor, Slovenia, eds. V. Rupnik, L. Zadnik-Stirn, S. Drobne, 111 - 116 (1999).
K. Cechlárová, V. Lacko, The kidney exchange problem: How hard is it to find a donor?, IM Preprint 4/2006 (2006).
Další literatura podle pokynů vedoucí.
Předběžná náplň práce
Cílem práce je implementovat existující heuristiky pro hledání stabilní permutace s krátkými cykly v problému výměny ledviny. Práce také může obsahovat návrh a implementaci vlastních vylepšení těchto heuristik, především z hlediska časové složitosti a praktické použitelnosti i pro velká vstupní data.
Předběžná náplň práce v anglickém jazyce
The aim of the thesis is to implement existing heuristics for finding a stable permutation with short cycles for the kidney exchange problem. The thesis may also contain a design and implementation of original improvements of these heuristics, especially with regard to time complexity and practical usability also for large input data.
- zadáno a potvrzeno stud. odd.