Abstrakt. Vi anser att problemet med att hitta en populär matchning i kapaciated House Allocation problem (CHA). Ett fall av CHA involverar en uppsättning agenter och en uppsättning hus. Varje agent har en preferenslista där en undergrupp av hus rankas i strikt ordning, och varje hus kan matchas till ett antal agenter som inte får överskrida sin kapacitet. En matchande M är populär om det inte finns någon annan matchande M sådan att antalet agenter som föredrar sin tilldelning i M till den i M överstiger antalet agenter som föredrar sin tilldelning i M till den i M. Här ger vi en O ( ε Cn1 + m) algoritm för att avgöra om en instans av CHA medger en populär matchning, och i så fall att hitta en största sådan matchning, där C är den totala kapaciteten hos husen, n1 är antalet agenter och m är den totala längden av agenternas preferenslistor. För det fall där preferenslistor kan innehålla band, ger vi en O(( ε C + n1)m) algoritm för det analoga problemet.
Manlove och Sng REF undersökte problemet med kapacierad bostadstilldelning, där husen har olika kapacitet.
Popular matchings in the capacitated house allocation problem
{'venue': 'In Proceedings of ESA 2006, the 14th Annual European Symposium on Algorithms, (LNCS 4168', 'journal': None, 'mag_field_of_study': ['Computer Science']}