Problems column

Samir Khuller*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


The stable marriage problem, displayed at the Symposium on Discrete Algorithms (SODA), which was held in New Orleans in January, 2007, is presented. The problem involves different sets of men and women, providing a rank-ordered preference list of members of the opposite sex. The aim of the problem is to find a matching, which eliminates blocking pairs. The paper presented by Iwama presents a generalization of the basic problem, where the preference list may have ties and include members of the opposite sex. The model says that finding a stable marriage without blocking pairs with the largest cardinality is NP-Complete. It was also observed that a local improvement-based approach offers an approximation factor of 1.8. The case, which presents G as a bipartite graph is known as Open shop Scheduling.

Original languageEnglish (US)
Article number1273351
JournalACM Transactions on Algorithms
Issue number3
StatePublished - Aug 1 2007

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


Dive into the research topics of 'Problems column'. Together they form a unique fingerprint.

Cite this