A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Model

1. Baïou, M., Balinski, M.: Erratum: The stable allocation (or ordinal transportation) problem. Math. Oper. Res. 27, 662–680 (2002)

   Article  MathSciNet  Google Scholar 

2. Eguchi, A., Fujishige, S.: An extension of the Gale-Shapley matching algorithm to a pair of M\(^{\natural}\) -concave functions, Discrete Mathematics and Systems Science Research Report 02-05, Osaka University (2002)

   Google Scholar 

3. Fleiner, T.: A matroid generalization of the stable matching polytope. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, pp. 105–114. Springer, Heidelberg (2001)

   Chapter  Google Scholar 

4. Fleiner, T.: Some results on stable matchings and fixed points, EGRES Technical Report 2002-08 (2002), http://www.cs.elte.hu/egres

5. Fleiner, T.: A fixed point approach to stable matchings and some applications. Math. Oper. Res. 28, 103–126 (2003)

   Article  MATH  MathSciNet  Google Scholar 

6. Fujishige, S., Yang, Z.: A note on Kelso and Crawford’s gross substitutes condition. Math. Oper. Res. (to appear)

   Google Scholar 

7. Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Amer. Math. Monthl 69, 9–15 (1962)

   Article  MATH  MathSciNet  Google Scholar 

8. Murota, K.: Convexity and Steinitz’s exchange property. Adv. Math. 124, 272–311 (1996)

   Article  MATH  MathSciNet  Google Scholar 

9. Murota, K.: Discrete convex analysis. Math. Programming 83, 313–371 (1998)

   MATH  MathSciNet  Google Scholar 

10. Murota, K.: Discrete Convex Analysis, Philadelphia. Society for Industrial and Applied Mathematics (2003)

    Google Scholar 

11. Murota, K., Shioura, A.: M-convex function on generalized polymatroid. Math. Oper. Res. 24, 95–105 (1999)

    Article  MATH  MathSciNet  Google Scholar 

12. Murota, K., Shioura, A.: Relationship of M-/L-convex functions with discrete convex functions by Miller and by Favati–Tardella. Discrete Appl. Math. 115, 151–176 (2001)

    Article  MATH  MathSciNet  Google Scholar 

13. Murota, K., Tamura, A.: New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities. Discrete Appl. Math. (to appear)

    Google Scholar 

14. Shioura, A.: Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem. Discrete Appl. Math. (to appear)

    Google Scholar 

15. Tamura, A.: Coordinatewise domain scaling algorithm for M-convex function minimization. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 21–35. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

Download references