Access count of this item: 62
|Title:||An improved approximation lower bound for finding almost stable maximum matchings|
|Author's alias:||濱田, 浩気|
The stable marriage problem
|Journal title:||Information Processing Letters|
|Abstract:||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 δ>1unless P=NP, even when all preference lists are of length at most 3. In this paper, we improve this constant δ to n(1−ε) for any ε>0, where n is the number of men in an input.|
|Rights:||© 2009. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
The full-text file will be made open to the public on 31 August 2011 in accordance with publisher's 'Terms and Conditions for Self-Archiving'
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
|Appears in Collections:||Journal Articles|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.