Det stabila äktenskapsproblemet och dess många varianter har studerats i stor utsträckning i litteraturen [6, 22, 15], delvis på grund av problemets inneboende dragningskraft, delvis på grund av elegansen i de tillhörande strukturerna och algoritmerna, och delvis på grund av viktiga praktiska tillämpningar, såsom National Resident Matching Program [20] och liknande storskaliga matchningsprogram. Här presenterar vi den första omfattande studien av varianter av problemet där preferenslistorna för deltagarna inte nödvändigtvis är fullständiga och inte nödvändigtvis helt beställda. Vi visar att under överraskande restriktiva antaganden är ett antal av dessa varianter svåra och svåra att uppskatta. Den viktigaste iakttagelsen är att, i motsats till det fall där preferenslistor är fullständiga eller strikt beställda (eller båda), ett givet problem instans kan tillåta stabila matchningar av olika storlekar. I detta sammanhang är exempel på problem som är svåra: hitta en stabil matchning av maximal eller minsta storlek, avgöra om ett visst par är stabilt - även om likgiltigheten tar formen av band på en sida bara, slipsarna är på svansen av listor, det finns som mest en slips per lista, och varje slips är av längd 2; och hitta, eller approximera, både en "egalitär" och en "minimum ånger" stabil matchning. Men vi ger en 2- approximation algoritm för problemen med att hitta en stabil matchning av maximal eller minsta storlek. Vi diskuterar också de betydande konsekvenserna av våra resultat för praktiska matchningssystem.
MAX-SMTI är känd för att vara N P-hård även om varje slips förekommer i slutet av vissa agent preferenslista, slipsar förekommer på en sida endast och varje slips är av längd två REF.
Hard variants of stable marriage
{'venue': 'THEORETICAL COMPUTER SCIENCE', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}