Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Study of Players’ Experiences During Brain Games Play Read chapter Read first chapter

2016 | OriginalPaper | Chapter

An Empirical Local Search for the Stable Marriage Problem

Authors : Hoang Huu Viet, Le Hong Trang, SeungGwan Lee, TaeChoong Chung

Published in: PRICAI 2016: Trends in Artificial Intelligence

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper proposes a local search algorithm to find the egalitarian and the sex-equal stable matchings in the stable marriage problem. Based on the dominance relation of stable matchings from the men’s point of view, our approach discovers the egalitarian and the sex-equal stable matchings from the man-optimal stable matching. By employing a breakmarriage strategy to find stable neighbor matchings of the current stable matching and moving to the best neighbor matching, our local search finds the solutions while moving towards the woman-optimal stable matching. Simulations show that our proposed algorithm is efficient for the stable marriage problem.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter 3-D Volume of Interest Based Image Classification
next chapter Instance Selection Method for Improving Graph-Based Semi-supervised Learning
Literature
1.
Abraham, D.J., Irving, R.W., Manlove, D.F.: The student-project allocation problem. In: Proceedings of the 14th International Symposium, pp. 474–484. Kyoto, Japan, December 2003
2.
Fleiner, T., Irving, R.W., Manlove, D.F.: Efficient algorithms for generalized stable marriage and roommates problems. Theor. Comput. Sci. 381(1–3), 162–176 (2007)MathSciNetCrossRefMATH
3.
4.
Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., Walsh, T.: Local search approaches in stable matching problems. Algorithms 6(1), 591–617 (2013)MathSciNetCrossRef
5.
6.
Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)MATH
7.
8.
9.
Iwama, K., Miyazaki, S., Yanagisawa, H.: Approximation algorithms for the sex-equal stable marriage problem. ACM Trans. Algorithms 7(1), 2:1–2:17 (2010)MathSciNetCrossRefMATH
10.
11.
Nakamura, M., Onaga, K., Kyan, S., Silva, M.: Genetic algorithm for sex-fairstable marriage problem. In: 1995 IEEE International Symposium on Circuits and Systems, ISCAS 1995, vol. 1, pp. 509–512. Seattle, WA, April 1995
12.
Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econ. 92(6), 991–1016 (1984)CrossRef
13.
Russel, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd edn. Pearson Education, Upper Saddle River (2010)
14.
Vien, N.A., Viet, N.H., Kim, H., Lee, S., Chung, T.: Ant colony based algorithm for stable marriage problem. Adv. Innov. Syst. Comput. Sci. Softw. Eng. 1, 457–461 (2007)CrossRef
Metadata
Title
An Empirical Local Search for the Stable Marriage Problem
Authors
Hoang Huu Viet
Le Hong Trang
SeungGwan Lee
TaeChoong Chung
Copyright Year
2016
Book
PRICAI 2016: Trends in Artificial Intelligence

Print ISBN: 978-3-319-42910-6

Electronic ISBN: 978-3-319-42911-3

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-42911-3_46

Premium Partner

    Image Credits