Downloads: 354

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  orcid (unconfirmed)
Yanagisawa, Hiroki
Author's alias: 岩間, 一雄
宮崎, 修一
柳澤, 弘揮
Keywords: The student project allocation problem
Stable matching
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.
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.