Finding large stable matchings

Article English OPEN
Irving, R.W.; Manlove, D.F.;
(2009)
  • Subject: QA75

When ties and incomplete preference lists are permitted in the stable marriage and hospitals/residents problems, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is known to be NP-hard, even under ve... View more
  • References (23)
    23 references, page 1 of 3

    [5] A. Erdil and H. Erkin. What's the matter with tie-breaking? Improving e ciency in school choice. American Economic Review, 98:669{689, 2008.

    [6] H.N. Gabow. An e cient reduction technique for degree-constrained subgraph and bidirected network ow problems. In Proceedings of STOC '83: the 15th Annual ACM Symposium on Theory of Computing, pages 448{456. ACM, 1983.

    [7] D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9{15, 1962.

    [8] D. Gale and M. Sotomayor. Some remarks on the stable matching problem. Discrete Applied Mathematics, 11:223{232, 1985.

    [9] D. Gus eld and R.W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.

    [10] M. Halldorsson, K. Iwama, S. Miyazaki, and H. Yanagisawa. Improved approximation of the stable marriage problem. ACM Transactions on Algorithms, 3(3), 2007. Article number 30.

    [11] M.M. Halldorsson, K. Iwama, S. Miyazaki, and H. Yanagisawa. Randomized approximation of the stable marriage problem. Theoretical Computer Science, 325(3):439{ 465, 2004.

    [12] R.W. Irving. Stable marriage and indi erence. Discrete Applied Mathematics, 48:261{ 272, 1994.

    [13] R.W. Irving and P. Leather. The complexity of counting stable marriages. SIAM Journal on Computing, 15(3):655{667, 1986.

    [14] R.W. Irving and D.F. Manlove. Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems. Journal of Combinatorial Optimization, 16(3):279{292, 2008.

  • Metrics
Share - Bookmark