Finding large stable matchings

Article English OPEN
Irving, R.W. ; Manlove, D.F. (2009)

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 very severe restrictions on the number, size, and position of ties. In this article, we present two new heuristics for finding large stable matchings in variants of these problems in which ties are on one side only. We describe an empirical study involving these heuristics and the best existing approximation algorithm for this problem. Our results indicate that all three of these algorithms perform significantly better than naive tie-breaking algorithms when applied to real-world and randomly-generated data sets and that one of the new heuristics fares slightly better than the other algorithms, in most cases. This study, and these particular problem variants, are motivated by important applications in large-scale centralized matching schemes.
  • 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.

  • Similar Research Results (3)
  • Metrics
    No metrics available
Share - Bookmark