A generalized Gale-Shapley algorithm for a discrete-concave stable-marriage model

Akinobu Eguchi, Satoru Fujishige, Akihisa Tamura

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


The stable marriage model due to Gale and Shapley is one of the most fundamental two-sided matching models. Recently, Kleiner generalized the model in terms of matroids, and Eguchi and Fujishige extended the matroidal model to the framework of discrete convex analysis. In this paper, we extend their model to a vector version in which indifference on preferences is allowed, and show the existence of a stable solution by a generalization of the Gale-Shapley algorithm.

Original languageEnglish
Pages (from-to)495-504
Number of pages10
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publication statusPublished - 2003 Dec 1
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A generalized Gale-Shapley algorithm for a discrete-concave stable-marriage model'. Together they form a unique fingerprint.

Cite this