Abstrakt. I den här artikeln behandlar vi problemet med sjukhusinvånare (HR) och sjukhusinvånarna problem med lägre kvoter (HRLQ). I denna modell med tvåsidiga preferenser är stabilitet en väl vedertagen uppfattning om optimalitet. I avsaknad av lägre kvoter behöver det dock inte finnas någon stabil och genomförbar matchning. För HRLQ-problemet är vårt mål därför att producera en bra genomförbar matchning förutsatt att en genomförbar matchning finns. Datamatchning med minsta antal blockerande par (Min-BP) och minsta antal blockerande invånare (Min-BR) är kända för att vara NP-Complete. De enda approximationsalgoritmerna för dessa problem fungerar under stränga restriktioner på preferenslistorna. Vi presenterar en algoritm som kringgår denna begränsning och beräknar en populär matchning i HRLQ instans. Vi visar att på data-uppsättningar som genereras med olika generatorer, vår algoritm fungerar mycket bra när det gäller att blockera par och blockera invånare. Yokoi [20] studerade nyligen avundsfria matchningar för HRLQ-problemet. Vi föreslår en enkel ändring av Yokois algoritm för att ge en maximal avundsfri matchning. Vi observerar att populära matchningar överträffar avundsfria matchningar på flera parametrar av praktisk betydelse, som storlek, antal blockerande par, antal blockerande invånare. I avsaknad av lägre kvoter, dvs. i problemet med sjukhusinvånare (HR), garanteras stabila matchningar. Även i detta fall visar vi att popularitet är ett praktiskt alternativ till stabilitet. Till exempel, på syntetiska data-uppsättningar som genereras med hjälp av en viss modell, liksom på verkliga världen data-uppsättningar, en populär matchning är i genomsnitt 8-10% större i storlek, matchar fler invånare till sin top-choice, och fler invånare föredrar den populära matchningen jämfört med en stabil matchning. Vår omfattande studie avslöjar den praktiska dragningskraften hos populära matchningar för HR- och HRLQ-problemen. Såvitt vi vet är detta den första studien om empirisk utvärdering av populära matchningar i denna miljö.
REF presenterar en algoritm för att beräkna en maximal avundsfri matchning som innehåller Yokois matchning, och ger även empiriska resultat.
G T ] 2 8 A pr 2 01 8 How good are Popular Matchings ?