O Problema do Casamento Estável com Restrições de Pares
Autores
|
1853 |
787,6
|
|
|
1854 |
787,6
|
Informações:
Publicações do PESC
O Problema do Casamento Estável com Restrições de Pares
Vânia Maria Félix Dias
Fevereiro/2000
| Orientador: | Jayme Luiz Szwarcfiter | |
| ||
O problema dos casamentos estáveis clássico foi apresentado por Gale & Shapley, em 1962. Os autores desenvolveram um algoritmo que encontra sempre uma solução específica do problema. Nesse mesmo trabalho, foi a- presentado o Problema dos Companheiros de Quarto, uma generalização do primeiro, que nem sempre admite solução. No presente trabalho, descreve- mos um algoritmo para encontrar um casamento estável com casais forçados e casais proibidos no problema clássico. Isto é, nesse casamento, necessaria- mente, alguns pares devem ser casados enquanto outros não podem formar um casal. O algoritmo proposto é eficiente, no sentido de que termina num tempo polinomial no tamanho da entrada. Tal algoritmo foi elaborado a partir de um teorema de caracterização, também aqui formulado. Além disso, estendemos essa caracterização para o problema dos companheiros de quarto.
Stable Matchings with Restricted Pairs
Vânia Maria Félix Dias
February/2000
| Advisor: | Jayme Luiz Szwarcfiter | |
| Department: Systems Engineering and Computer Science | ||
The classical stable marriage problem was introduced by Gale & Shapley, in 1962. The authors developed an algorithm that always finds a specific solution for this problem. Also in this work, was presented the roommates problem, a generalization of the former, that not always admits a solution. In the present work, we propose an algorithm to find a stable matching with forced and forbidden pairs for the classical problem. That is, in this matching, necessarily some pairs are partners and other cannot be partners. The proposed algorithm is efficient, in the sense that it terminates within a time which is polynomial in the size of the input. Such algorithm is based on a characterization theorem, also here presented. Furthermore, we extend this characterization to the roommates problem.