Paper ID: 9113
Size versus stability in the Marriage problem
Biro,P.
Manlove,D.F.
Mittal,S.
Publication Type:
Conference Proceedings
Appeared in:
Proceedings of WAOA 2008: the 6th Workshop on
Approximation and Online Algorithms, volume 5426
of Lecture Notes in Computer Science
Page Numbers : 1528
Publisher: Springer
Year: 2009
ISBN/ISSN:
URL: This publication is available at this URL.
Abstract:
Given an instance I of the classical Stable Marriage problem
with Incomplete preference lists (SMI), a maximum
cardinality matching can be larger than a stable matching.
In many largescale applications of SMI, we seek to match as
many agents as possible. This motivates the problem of
finding a maximum cardinality matching in I that admits the
smallest number of blocking pairs (so is "as stable as
possible"). We show that this problem is NPhard and not
approximable within n^{1\varepsilon}, for any
\varepsilon>0, unless P=NP, where n is the number of men in
I. Further, even if all preference lists are of length at
most 3, we show that the problem remains NPhard and not
approximable within \delta, for some \delta>1. By contrast,
we give a polynomialtime algorithm for the case where the
preference lists of one sex are of length at most 2.
