Vi introducerar det klassade stabila matchningsproblemet, ett problem som motiveras av akademisk anställning. Anta att ett antal institut anställer fakultetsmedlemmar från en pool av sökande. Både institut och sökande har företräde framför den andra sidan. Ett institut klassificerar de sökande utifrån deras forskningsområden (eller något annat kriterium), och för varje klass sätter det en lägre gräns och en övre gräns för antalet sökande som det skulle anställa i den klassen. Målet är att hitta en stabil matchning från vilken ingen grupp av deltagare har anledning att avvika. Dessutom bör matchningen respektera klassernas övre/lägre gränser. I den första delen av tidningen studerar vi klassade stabila matchningsproblem vars klassificeringar tillhör en fast uppsättning "ordertyper". Vi visar att om uppsättningen helt består av nedgående skogar finns det en polynomtidsalgoritm; annars är det NP-komplett att bestämma förekomsten av en stabil matchning. I den andra delen undersöker vi problemet med hjälp av en polyhedral strategi. Antag att alla klassificeringar är laminära familjer och att det inte finns någon lägre gräns. Vi föreslår en uppsättning linjära ojämlikheter för att beskriva stabil matchande polytop och bevisa att den är integrerad. Detta integrality resultat gör att vi kan hitta optimala stabila matchningar i polynom tid med hjälp av Ellipsoid algoritm; dessutom ger det en beskrivning av den stabila matchande polytop för många-till-många (oklassificerade) stabila matchning problem, och därmed svara på en öppen fråga från Sethuraman, Teo och Qian.
Classified Stable Matching problem (CSM), föreslås av Huang REF, är en generalisering av HR-LQ utan sjukhus stängningar.
Classified stable matching
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}