Problems column

Samir Khuller

doi:10.1145/1273340.1273351

Problems column

Samir Khuller^*

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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 language	English (US)
Article number	1273351
Journal	ACM Transactions on Algorithms
Volume	3
Issue number	3
DOIs	https://doi.org/10.1145/1273340.1273351
State	Published - Aug 1 2007

ASJC Scopus subject areas

Mathematics (miscellaneous)

Access to Document

10.1145/1273340.1273351

Cite this

@article{51bec06dc2cb4c7cb4ca27b13aae7740,

title = "Problems column",

abstract = "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.",

author = "Samir Khuller",

year = "2007",

month = aug,

day = "1",

doi = "10.1145/1273340.1273351",

language = "English (US)",

volume = "3",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "3",

}

TY - JOUR

T1 - Problems column

AU - Khuller, Samir

PY - 2007/8/1

Y1 - 2007/8/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34548282954&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34548282954&partnerID=8YFLogxK

U2 - 10.1145/1273340.1273351

DO - 10.1145/1273340.1273351

M3 - Article

AN - SCOPUS:34548282954

SN - 1549-6325

VL - 3

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 3

M1 - 1273351

ER -

Problems column

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this