Access count of this item: 219

Files in This Item:
File Description SizeFormat 
j.jda.2012.02.001.pdf141.34 kBAdobe PDFView/Open
Title: Improved approximation bounds for the Student-Project Allocation problem with preferences over projects
Authors: Iwama, Kazuo  kyouindb  KAKEN_id
Miyazaki, Shuichi  kyouindb  KAKEN_id
Yanagisawa, Hiroki
Author's alias: 岩間, 一雄
宮崎, 修一
柳澤, 弘揮
Keywords: The student project allocation problem
Stable matching
NP-hardness
Approximation algorithm
Approximation ratio
Issue Date: May-2012
Publisher: Elsevier B.V.
Journal title: Journal of Discrete Algorithms
Volume: 13
Start page: 59
End page: 66
Abstract: Manlove and OʼMalley (2008) proposed the Student-Project Allocation problem with Preferences over Projects (SPA-P). They proved that the problem of finding a maximum stable matching in SPA-P is APX-hard and gave a polynomial-time 2-approximation algorithm. In this paper, we give an improved upper bound of 1.5 and a lower bound of 21/19 (>1.1052).
Rights: © 2012 Elsevier B.V.
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
URI: http://hdl.handle.net/2433/155464
DOI(Published Version): 10.1016/j.jda.2012.02.001
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.