Vi studerar problemet med att hitta stora svagt stabila matchningar när preferenslistor är ofullständiga och innehåller ensidiga band. Computing maximal svagt stabila matchningar är känd för att vara NP-hård. Vi presenterar en polynom-tidsalgoritm som uppnår en förbättrad approximationsgrad på 1 + 1/e. Liksom ett antal befintliga approximationsalgoritmer för detta problem, är vår algoritm baserad på en förslagsprocess där numeriska prioriteringar justeras enligt lösningen av ett linjärt program, och används för tiebreaking ändamål. Vår huvudidé är att använda en oändligt liten stegstorlek för att öka prioriteringarna. Vår analys handlar om att lösa ett oändligt-dimensionellt faktor-uppenbarande linjärt program. Vi visar också att förhållandet 1 + 1/e är en övre gräns för integratet gap, som matchar den kända nedre gränsen.
Lam och Plaxton REF studerade problemet med att hitta stora svagt stabila matchningar när preferenslistor är ofullständiga och innehåller ensidiga kopplingar och presenterade en 1 + 1/e-faktor approximationsalgoritm.
A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Computer Science']}