Access count of this item: 62

Files in This Item:
File Description SizeFormat 
j.ipl.2009.06.008.pdf136.3 kBAdobe PDFView/Open
Title: An improved approximation lower bound for finding almost stable maximum matchings
Authors: Hamada, Koki
Iwama, Kazuo
Miyazaki, Shuichi  kyouindb  KAKEN_id
Author's alias: 濱田, 浩気
岩間, 一雄
宮崎, 修一
Keywords: Approximation algorithms
The stable marriage problem
Approximation ratio
Polynomial-time reduction
Issue Date: 31-Aug-2009
Publisher: Elsevier BV
Journal title: Information Processing Letters
Volume: 109
Issue: 18
Start page: 1036
End page: 1040
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
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. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
DOI(Published Version): 10.1016/j.ipl.2009.06.008
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks

Export Format: 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.