Skip to main content
SpringerLink
Log in

Parameterized Complexity and Local Search Approaches for the Stable Marriage Problem with Ties

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We consider the variant of the classical Stable Marriage problem where preference lists can be incomplete and may contain ties. In such a setting, finding a stable matching of maximum size is NP-hard. We study the parameterized complexity of this problem, where the parameter can be the number of ties, the maximum or the overall length of ties. We also investigate the applicability of a local search algorithm for the problem. Finally, we examine the possibilities for giving an FPT algorithm or an FPT approximation algorithm for finding an egalitarian or a minimum regret matching.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aarts, E.H.L., Lenstra, J.K. (eds.): Local Search in Combinatorial Optimization. Wiley, New York (1997)

    MATH  Google Scholar 

  2. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)

    Google Scholar 

  3. Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)

    Google Scholar 

  4. Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9–15 (1962)

    Article  MATH  MathSciNet  Google Scholar 

  5. Gusfield, D.: Three fast algorithms for four problems in stable marriage. SIAM J. Comput. 16(1), 111–128 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  6. Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)

    MATH  Google Scholar 

  7. Halldórsson, M.M., Irving, R.W., Iwama, K., Manlove, D.F., Miyazaki, S., Morita, Y., Scott, S.: Approximability results for stable marriage problems with ties. Theor. Comput. Sci. 306(1–3), 431–447 (2003)

    Article  MATH  Google Scholar 

  8. Irving, R.W.: Stable marriage and indifference. Discrete Appl. Math. 48(3), 261–272 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  9. Irving, R.W., Manlove, D.F.: Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems. J. Comb. Optim. 16(3), 279–292 (2008). doi:10.1007/s10878-007-9133-x

    Article  MATH  MathSciNet  Google Scholar 

  10. Irving, R.W., Leather, P., Gusfield, D.: An efficient algorithm for the “optimal” stable marriage. J. ACM 34(3), 532–543 (1987)

    MathSciNet  Google Scholar 

  11. Iwama, K., Manlove, D., Miyazaki, S., Morita, Y.: Stable marriage with incomplete lists and ties. In: ICALP’99. LNCS, vol. 1644, pp. 443–452. Springer, Berlin (1999)

    Google Scholar 

  12. Khuller, S., Bhatia, R., Pless, R.: On local search and placement of meters in networks. SIAM J. Comput. 32(2), 470–487 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  13. Király, Z.: Better and simpler approximation algorithms for the stable marriage problem. In: ESA 2008. LNCS, vol. 5193, pp. 623–634. Springer, Berlin (2008)

    Chapter  Google Scholar 

  14. Krokhin, A., Marx, D.: On the hardness of losing weight. In: ICALP 2008. LNCS, vol. 5125, pp. 662–673. Springer, Berlin (2008)

    Google Scholar 

  15. Manlove, D.F., Irving, R.W., Iwama, K., Miyazaki, S., Morita, Y.: Hard variants of stable marriage. Theor. Comput. Sci. 276(1–2), 261–279 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  16. Marx, D.: Local search. Parameterized Complexity News 3, 7–8 (2008)

    Google Scholar 

  17. Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60–78 (2008)

    Article  Google Scholar 

  18. Marx, D.: Searching the k-change neighborhood for TSP is W[1]-hard. Oper. Res. Lett. 36(1), 31–36 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  19. Marx, D., Schlotter, I.: Stable assignment with couples: parameterized complexity and local search. Manuscript

  20. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)

    Book  MATH  Google Scholar 

  21. Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econ. 92, 991–1016 (1984)

    Article  Google Scholar 

  22. Roth, A.E., Sotomayor, M.: Two Sided Matching: A Study in Game-Theoretic Modelling and Analysis. Cambridge University Press, Cambridge (1990)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Information Theory, Budapest University of Technology and Economics, 1521, Budapest, Hungary

    Dániel Marx & Ildikó Schlotter

Authors
  1. Dániel Marx
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ildikó Schlotter
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ildikó Schlotter.

Additional information

Research funded by the Hungarian National Research Fund (OTKA grant K 67651). The first author is supported by Magyary Zoltán Felsöoktatási Közalapítvány.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Marx, D., Schlotter, I. Parameterized Complexity and Local Search Approaches for the Stable Marriage Problem with Ties. Algorithmica 58, 170–187 (2010). https://doi.org/10.1007/s00453-009-9326-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-009-9326-z

Keywords

Search

Navigation