Pagina Radice del Progetto: Stable Matching e Roommates Problem

Dato un grafo bipartito con maschietti a sinistra e femminucce a destra, si assuma che ad ogni soggetto risulti associata una lista dei partners ammissibili, ordinati per preferenza da parte del soggetto stesso. Uno stable matching è un accoppiamento M tale che non esista una coppia maschio/femmina, tale che entrambi i soggetti della coppia si preferiscano rispetto ai rispettivi partners assegnati loro in M. Galey e Shapley, con il loro famoso "proposal algorithm" hanno dimostrato che esiste sempre uno stable matching ed hanno mostrato come trovarne uno in tempo lineare. Vorremmo innanzittutto codificare il loro algoritmo in noweb e c++.

Come riferimento, consiglio:

Knuth, Donald E.
Stable marriage and its relation to other combinatorial problems. An introduction to the mathematical analysis of algorithms.
CRM Proceedings & Lecture Notes, 10. American Mathematical Society, Providence, RI, 1997.
ISBN: 0-8218-0603-3

La naturale estensione di questo problema a grafi non bipartiti è nota col nome del "roommates problem". Anche per tale problema è stato proposto un algoritmo:

Irving, Robert
An efficient algorithm for the "stable roommates" problem.
J. Algorithms 6 (1985), no. 4, 577--595.

Tale articolo include inoltre una descrizione dell'algoritmo in Pascal. Anche di questo algoritmo vogliamo dare un'implementazione in noweb e c++.

Lo sforzo implementativo per questo progetto dovrebbe rimanere contenuto. Ci sono tuttavia ampie possibilità per spaziare sul piano culturale e scientifico, in seno alla documentazione del progetto.

Possibili letture:

Gusfield, Dan
The structure of the stable roommate problem: efficient representation and enumeration of all stable assignments.
SIAM J. Comput. 17 (1988), no. 4, 742--769.

Chung, Kim-Sau
On the existence of stable roommate matchings.
Games Econom. Behav. 33 (2000), no. 2, 206--230.

created: 25 Aprile 2001
updated: 25 Aprile 2001