An improved approximation lower bound for finding almost stable maximum matchings

In the stable marriage problem that allows incomplete preference lists, all stable matchings for a given instance have the same size. However, if we ignore the stability, there can be larger matchings. Biró et al. defined the problem of finding a maximum cardinality matching that contains minimum number of blocking pairs. They proved that this problem is not approximable within some constant δ>1 unless P=NP, even when all preference lists are of length at most 3. In this paper, we improve this constant δ to n1−ε for any ε>0, where n is the number of men in an input.