Years and Authors of Summarized Original Work
-
2000; Eguchi, Fujishige, Tamura, Fleiner
Problem Definition
In the stable marriage problem first defined by Gale and Shapley [7], there is one set each of men and women having the same size, and each person has a strict preference order on persons of the opposite gender. The problem is to find a matching such that there is no pair of a man and a woman who prefer each other to their partners in the matching. Such a matching is called a stable marriage (or stable matching). Gale and Shapley showed the existence of a stable marriage and gave an algorithm for finding one. Fleiner [4] extended the stable marriage problem to the framework of matroids, and Eguchi, Fujishige, and Tamura [3] extended this formulation to a more general one in terms of discrete convex analysis, which was developed by Murota [8, 9]. Their formulation is described as follows.
Let M and Wbe sets of men and women who attend a dance party at which each person dances a...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Abraham DJ, Irving RW, Manlove DF (2007) Two algorithms for the student-project allocation problem. J Discret Algorithms 5:73–90
Baïou M, Balinski, M (2002) Erratum: the stable allocation (or ordinal transportation) problem. Math Oper Res 27:662–680
Eguchi A, Fujishige S, Tamura A (2003) A generalized Gale-Shapley algorithm for a discrete-concave stable-marriage model. In: Ibaraki T, Katoh N, Ono H (eds) Algorithms and computation: 14th international symposium (ISAAC 2003), Kyoto. LNCS, vol 2906. Springer, Berlin, pp 495–504
Fleiner T (2001) A matroid generalization of the stable matching polytope. In: Gerards B, Aardal K (eds) Integer programming and combinatorial optimization: 8th international IPCO conference, Utrecht. LNCS, vol 2081. Springer, Berlin, pp 105–114
Fleiner T (2003) A fixed point approach to stable matchings and some applications. Math Oper Res 28:103–126
Fujishige S, Tamura A (2007) A two-sided discrete-concave market with bounded side payments: an approach by discrete convex analysis. Math Oper Res 32:136–155
Gale D, Shapley SL (1962) College admissions and the stability of marriage. Am Math Mon 69:9–15
Murota K (1998) Discrete convex analysis. Math Program 83:313–371
Murota K (2003) Discrete convex analysis. Society for Industrial and Applied Mathematics, Philadelphia
Shapley SL, Shubik M (1971) The assignment game I: the core. Int J Game Theor 1:111–130
Shioura A (2004) Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem. Discret Appl Math 134:303–316
Tamura A (2005) Coordinatewise domain scaling algorithm for M-convex function minimization. Math Program 102:339–354
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry
Tamura, A. (2016). Stable Marriage and Discrete Convex Analysis. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_394
Download citation
DOI: https://doi.org/10.1007/978-1-4939-2864-4_394
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-2863-7
Online ISBN: 978-1-4939-2864-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering