Problemet med att hitta en största stabil matchning där preferenslistor kan innehålla band och oacceptabla partners (MAX SMTI) är känt för att vara NP-hård. Den kan inte approximeras inom 33/29 (>1.1379) om inte P = NP, och den nuvarande bästa approximationsalgoritmen uppnår förhållandet 1.5. MAX SMTI förblir NPhard även när preferenslistor på en sida inte innehåller band, och det kan inte approximeras inom 21/19 (>1.1052) om inte P = NP. Även inom ramen för denna begränsning är den mest kända approximationskvoten emellertid fortfarande 1,5. I detta dokument förbättrar vi det till 25/17 (<1.4706). Det stabila äktenskapsproblemet · Det stabila äktenskapet med band och ofullständiga listor · Tillnärmningsalgoritm · Integerprogram · Linjär programavkoppling · Integrality gap
Nyligen, i REF, Iwama et al. förbättra approximationen till 25 17 för fall med ensidiga band.
A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}