Vi studerar problemet med att tilldela studenter till projekt, där både studenter och föreläsare har preferenser framför projekt, och både projekt och föreläsare har kapacitet. I detta sammanhang söker vi en stabil matchning mellan studenter och projekt, som respekterar dessa preferens- och kapacitetsbegränsningar. Här generaliserar stabilitetsdefinitionen motsvarande begrepp i samband med problemet med de klassiska sjukhusen/invånarna. Vi visar att stabila matchningar kan ha olika storlekar, vilket motiverar max-spa-p, problemet med att hitta en maximal kardinality stabil matchning. Vi bevisar att max-spa-p är NP-hård och inte ungefärlig inom δ, för vissa δ > 1, om inte P=NP. Å andra sidan ger vi en approximationsalgoritm med en prestandagaranti på 2 för max-spa-p.
Ref. REF studerade SPA-problemet där studenter och föreläsare har preferenser framför projekt.
Student project allocation with preferences over projects
{'venue': 'In Proceedings of ACID 2005: the 1st Algorithms and Complexity in Durham workshop, volume 4 of Texts in Algorithmics', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}