Paper ID: 8904
DCS Tech Report Number: TR2008283
Size Versus Stability in the Marriage Problem
Biro,P.
Manlove,D.F.
Mittal,S.
Publication Type:
Tech Report (internal)
Appeared in:
DCS Technical Report Series
Page Numbers :
Publisher: Dept of Computing Science, University of Glasgow
Year: 2008
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.
