Algoritmi per la ricerca di matching stabili

Il contenuto di questo documento verte sullo studio di algoritmi per la ricerca di matching stabili. Per risolvere tale problema ci basiamo sui grafi bipartiti e teniamo conto delle liste di preferenza dei membri che formano l’insieme nodi. Le liste accettabili possono anche avere pareggi, cioè indifferenza tra due elementi dell’altro insieme. In seguito a una breve introduzione di carattere storico viene presentato l’algoritmo di Gale-Shapley, l’algoritmo di base per risolvere il problema nel caso in cui le liste vengano presentate dai membri, di entrambi gli insiemi, con preferenze esclusivamente strette. In un secondo momento, dopo aver dimostrato che un matching popolare è anche stabile, si passa alla ricerca di un matching popolare di cardinalitá massima nel caso in cui le liste vengano presentate dai membri di uno solo dei due insiemi, eventualmente anche con pareggi. Trattandosi di una situazione diversa da quella introduttiva gli algoritmi presentati saranno del tutto diversi da quello di Gale-Shapley. Infine viene trattata la ricerca di un marching popolare, in un grafo bipartito, in cui le liste di preferenze vengono presentate da tutti i membri dei due insiemi. In questo caso però le liste ammettono anche i pareggi. La situazione è molto simile a quella di base, di conseguenza l’algoritmo presentato si basa su quello di Gale-Shapley. Si nota immediatamente che una leggera modifica nelle condizioni iniziali, come ad esempio l’ammissione di pareggi nelle liste di preferenze, porta a grandi differenze negli algoritmi sia a livello di struttura che a livello di complessità computazionale.