Student-Projekt Tilldelningsproblem med föreläsare preferenser över Studenter (spa-s) omfattar tre uppsättningar av agenter, nämligen studenter, projekt och föreläsare, där studenter har preferenser framför projekt och föreläsare har preferenser framför studenter. I detta scenario söker vi en stabil matchning, det vill säga en uppgift för studenter till projekt så att det inte finns någon student och föreläsare som har incitament att avvika från sina tilldelade. Vi studerar spa-st, utvidgningen av spa-s där preferenslistor över studenter och föreläsare inte behöver vara strikt beställda, och kan innehålla band. I detta scenario, stabila matchningar kan vara av olika storlekar, och det är känt att max spa-st, problemet med att hitta en maximal stabil matchning i spa-st, är NP-hård. Vi presenterar en linjär tid 3 2 - approximation algoritm för max spa-st och en Integer Programmering (IP) modell för att lösa max spa-st optimalt. Vi jämför approximationsalgoritmen med IP-modellen experimentellt med slumpmässigt genererade data. Vi finner att prestandan av approximationsalgoritmen lätt överträffade 3 2 bundet, bygga en stabil matchning inom 92% av optimal i alla fall, med procentsatsen är mycket högre för många fall. ACM Ämnesklassificeringsteori för beräkning → Utformning och analys av algoritmer
Nyligen, Cooper och Manlove REF har sett över problemet med att tilldela studenter till projekt, där både studenter och föreläsare har preferenser framför varandra, och föreläsare och projekt har övre kapacitetsbegränsningar.
A 3/2-approximation algorithm for the Student-Project Allocation problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}