Access count of this item: 138

Files in This Item:
File Description SizeFormat 
s00453-012-9699-2.pdf139.98 kBAdobe PDFView/Open
Title: A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
Authors: Iwama, Kazuo
Miyazaki, Shuichi  kyouindb  KAKEN_id
Yanagisawa, Hiroki
Author's alias: 岩間, 一雄
宮崎, 修一
柳澤, 弘揮
Keywords: The stable marriage problem
The stable marriage with ties and incomplete lists
Approximation algorithm
Integer program
Linear program relaxation
Integrality gap
Issue Date: Mar-2014
Publisher: Springer US
Journal title: Algorithmica
Volume: 68
Issue: 3
Start page: 758
End page: 775
Abstract: The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (>1.1379) unless P=NP, and the current best approximation algorithm achieves the ratio of 1.5. MAX SMTI remains NP-hard even when preference lists of one side do not contain ties, and it cannot be approximated within 21/19 (>1.1052) unless P=NP. However, even under this restriction, the best known approximation ratio is still 1.5. In this paper, we improve it to 25/17 (<1.4706).
Rights: The final publication is available at Springer via
The full-text file will be made open to the public on 01 March 2015 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.1007/s00453-012-9699-2
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.