Approximability results for stable marriage problems with ties

Magnús M. Halldórsson; Robert W. Irving; Kazuo Iwama; David F. Manlove; Shuichi Miyazaki; Yasufumi Morita; Sandy Scott

doi:10.1016/S0304-3975(03)00321-9

Approximability results for stable marriage problems with ties

Magnús M. Halldórsson, Robert W. Irving, Kazuo Iwama, David F. Manlove, Shuichi Miyazaki, Yasufumi Morita, Sandy Scott

Department of Computer Science

Reykjavik University

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

Abstract

We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds hold for the approximability of each of the problems of finding an egalitarian, minimum regret and sex-equal stable matching. We also consider stable marriage instances in which persons may express unacceptable partners in addition to ties. In this setting, we prove that there are constants δ, δ′ such that each of the problems of approximating a maximum and minimum cardinality stable matching within factors of δ, δ′ (respectively) is NP-hard, under strong restrictions. We also give an approximation algorithm for both problems that has a performance guarantee expressible in terms of the number of lists with ties. This significantly improves on the best-known previous performance guarantee, for the case that the ties are sparse. Our results have applications to large-scale centralized matching schemes.

Original language	English
Pages (from-to)	431-447
Number of pages	17
Journal	Theoretical Computer Science
Volume	306
Issue number	1-3
DOIs	https://doi.org/10.1016/S0304-3975(03)00321-9
Publication status	Published - 5 Sept 2003

Bibliographical note

Funding Information: Keywords: Stable marriage problem; Ties; Unacceptable partners; Inapproximability results; Approximation algorithm An earlier version of a part of this paper appeared in [8]. ∗Corresponding author. Tel.: +44-141-330-2794; fax: +44-141-330-4913. E-mail addresses: [email protected] (M.M. Halldo'rsson), [email protected] (R.W. Irving), iwama@kuis. kyoto-u.ac.jp (K. Iwama), [email protected] (D.F. Manlove), [email protected] (S. Miyazaki), [email protected] (Y. Morita), [email protected] (S. Scott). 1Supported in part by Scienti9c Research Grant, Ministry of Japan, 13480081. 2Supported by award NUF-NAL-02 from the NuLeld Foundation and grant GR/R84597/01 from the Engineering and Physical Sciences Research Council.

Other keywords

Approximation algorithm
Inapproximability results
Stable marriage problem
Ties
Unacceptable partners

Access to Document

10.1016/S0304-3975(03)00321-9

Cite this

@article{fe41731d52b84b8fafd9fef47b2ffda1,

title = "Approximability results for stable marriage problems with ties",

abstract = "We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds hold for the approximability of each of the problems of finding an egalitarian, minimum regret and sex-equal stable matching. We also consider stable marriage instances in which persons may express unacceptable partners in addition to ties. In this setting, we prove that there are constants δ, δ′ such that each of the problems of approximating a maximum and minimum cardinality stable matching within factors of δ, δ′ (respectively) is NP-hard, under strong restrictions. We also give an approximation algorithm for both problems that has a performance guarantee expressible in terms of the number of lists with ties. This significantly improves on the best-known previous performance guarantee, for the case that the ties are sparse. Our results have applications to large-scale centralized matching schemes.",

keywords = "Approximation algorithm, Inapproximability results, Stable marriage problem, Ties, Unacceptable partners",

author = "Halld{\'o}rsson, \{Magn{\'u}s M.\} and Irving, \{Robert W.\} and Kazuo Iwama and Manlove, \{David F.\} and Shuichi Miyazaki and Yasufumi Morita and Sandy Scott",

note = "Funding Information: Keywords: Stable marriage problem; Ties; Unacceptable partners; Inapproximability results; Approximation algorithm An earlier version of a part of this paper appeared in [8]. ∗Corresponding author. Tel.: +44-141-330-2794; fax: +44-141-330-4913. E-mail addresses: [email protected] (M.M. Halldo'rsson), [email protected] (R.W. Irving), iwama@kuis. kyoto-u.ac.jp (K. Iwama), [email protected] (D.F. Manlove), [email protected] (S. Miyazaki), [email protected] (Y. Morita), [email protected] (S. Scott). 1Supported in part by Scienti9c Research Grant, Ministry of Japan, 13480081. 2Supported by award NUF-NAL-02 from the NuLeld Foundation and grant GR/R84597/01 from the Engineering and Physical Sciences Research Council.",

year = "2003",

month = sep,

day = "5",

doi = "10.1016/S0304-3975(03)00321-9",

language = "English",

volume = "306",

pages = "431--447",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Approximability results for stable marriage problems with ties

AU - Halldórsson, Magnús M.

AU - Irving, Robert W.

AU - Iwama, Kazuo

AU - Manlove, David F.

AU - Miyazaki, Shuichi

AU - Morita, Yasufumi

AU - Scott, Sandy

N1 - Funding Information: Keywords: Stable marriage problem; Ties; Unacceptable partners; Inapproximability results; Approximation algorithm An earlier version of a part of this paper appeared in [8]. ∗Corresponding author. Tel.: +44-141-330-2794; fax: +44-141-330-4913. E-mail addresses: [email protected] (M.M. Halldo'rsson), [email protected] (R.W. Irving), iwama@kuis. kyoto-u.ac.jp (K. Iwama), [email protected] (D.F. Manlove), [email protected] (S. Miyazaki), [email protected] (Y. Morita), [email protected] (S. Scott). 1Supported in part by Scienti9c Research Grant, Ministry of Japan, 13480081. 2Supported by award NUF-NAL-02 from the NuLeld Foundation and grant GR/R84597/01 from the Engineering and Physical Sciences Research Council.

PY - 2003/9/5

Y1 - 2003/9/5

N2 - We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds hold for the approximability of each of the problems of finding an egalitarian, minimum regret and sex-equal stable matching. We also consider stable marriage instances in which persons may express unacceptable partners in addition to ties. In this setting, we prove that there are constants δ, δ′ such that each of the problems of approximating a maximum and minimum cardinality stable matching within factors of δ, δ′ (respectively) is NP-hard, under strong restrictions. We also give an approximation algorithm for both problems that has a performance guarantee expressible in terms of the number of lists with ties. This significantly improves on the best-known previous performance guarantee, for the case that the ties are sparse. Our results have applications to large-scale centralized matching schemes.

AB - We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds hold for the approximability of each of the problems of finding an egalitarian, minimum regret and sex-equal stable matching. We also consider stable marriage instances in which persons may express unacceptable partners in addition to ties. In this setting, we prove that there are constants δ, δ′ such that each of the problems of approximating a maximum and minimum cardinality stable matching within factors of δ, δ′ (respectively) is NP-hard, under strong restrictions. We also give an approximation algorithm for both problems that has a performance guarantee expressible in terms of the number of lists with ties. This significantly improves on the best-known previous performance guarantee, for the case that the ties are sparse. Our results have applications to large-scale centralized matching schemes.

KW - Approximation algorithm

KW - Inapproximability results

KW - Stable marriage problem

KW - Ties

KW - Unacceptable partners

UR - https://www.scopus.com/pages/publications/0041387618

U2 - 10.1016/S0304-3975(03)00321-9

DO - 10.1016/S0304-3975(03)00321-9

M3 - Article

SN - 0304-3975

VL - 306

SP - 431

EP - 447

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-3

ER -

Approximability results for stable marriage problems with ties

Abstract

Bibliographical note

Other keywords

Access to Document

Fingerprint

Cite this