Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
From the famous Gale–Shapley theorem we know that each classical marriage problem admits at least one stable matching. This fact has inspired researchers to search for the maximum number of possible stable matchings, which is equivalent to finding the minimum number of unstable matchings among all such problems of size n. In this paper, we deal with this issue for the Gale–Shapley model with preferences represented by arbitrary partial orders. Also, we discuss this model in the context of the classical Gale–Shapley model.
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
5--15
Opis fizyczny
Bibliogr. 10 poz., rys.
Twórcy
autor
- Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, ul. Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
Bibliografia
- [1] DRGAS-BURCHARDT E., ŚWITALSKI Z., A number of stable matchings in models of the Gale–Shapley type, Discrete Applied Mathematics, 2013, 162 (18), 2932–2936.
- [2] GALE D., SHAPLEY L.S., College Admissions and the Stability of Marriage, American Mathematical Monthly, 1962, 69, 9–15.
- [3] GUSFIELD D., IRVING R.W., The Stable Marriage Problem: Structure and Algorithms, MIT Press, Cambridge, MA, 1989.
- [4] IRVING R.W., LEATHER P., The complexity of counting stable marriages, SIAM Journal on Computing, 1986, 15, 655–667.
- [5] IRVING R.W., Stable marriage and indifference, Discrete Applied Mathematics, 1994, 48, 261–272.
- [6] KNUTH D.E., Mariages Stables, Les Presses de l’Université de Montréal, Montréal 1976.
- [7] MANLOVE D.F., IRVING R.W., IWAMA K., MIYAZAKI S., MORITA Y., Hard variants of stable marriage, Theoretical Computer Science, 2002, 276, 261–279.
- [8] PITTEL B., The Average Number of Stable Matchings, SIAM Journal on Discrete Mathematics, 1989, 2–4, 530–549.
- [9] ROTH A.E., SOTOMAYOR M.A.O., Two-sided matchings, A study in game-theoretic modeling and analysis, Econometric Society Monographs, 18, 2003.
- [10] THURBER E.G., Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Mathematics, 2002, 248, 195–219.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-c2976732-9115-4146-bc0f-4a0c4125d20d