Stabilità rilassata in problemi di matching bipartiti

Lo scopo di questo elaborato è quello mostrare strategie di rilassamento della stabilità per diverse tipologie di problemi di grafi bipartiti. In primo luogo affronteremo il problema MAX HRSS, presentando un algoritmo di approssimazione per combattere la NP-difficoltà del problema. Successivamente, tratteremo casi speciali dello stesso problema MAX HRSS interessanti per la loro risolvibilità in tempo polinomiale. Per poi concludere studiando problemi in matching bipartiti con pesi sugli archi, dove i pesi rappresentano l'importanza di includere o meno tale arco nel matching. Presenteremo una strategia di rilassatezza della stabilità basata sul pagare un prezzo per gli archi bloccanti del matching, massimizzando il valore dato dal peso degli archi del matching meno il costo degli archi bloccanti. Infine, mostreremo che ci sono casi in cui questa strategia porta ad algoritmi risolutivi polinomiali.