Access count of this item: 55

Files in This Item:
File Description SizeFormat 
978-3-642-20877-5_43.pdf171.58 kBAdobe PDFView/Open
Title: Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects
Authors: Iwama, Kazuo
Miyazaki, Shuichi  kyouindb  KAKEN_id
Yanagisawa, Hiroki
Author's alias: 岩間, 一雄
宮崎, 修一
柳澤, 弘揮
Issue Date: 2011
Publisher: Springer Berlin Heidelberg
Journal title: Lecture Notes in Computer Science
Volume: 6648
Start page: 440
End page: 451
Abstract: Manlove and O’Malley [9] 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)21/19 (>1.1052) .
Description: 'Theory and Applications of Models of Computation' 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings
Rights: The final publication is available at Springer via https://doi.org/10.1007/978-3-319-18173-8_27
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
URI: http://hdl.handle.net/2433/226946
DOI(Published Version): 10.1007/978-3-642-20877-5_43
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.