Downloads: 366

Files in This Item:
File Description SizeFormat 
j.jda.2012.02.001.pdf141.34 kBAdobe PDFView/Open
Full metadata record
DC FieldValueLanguage
dc.contributor.authorIwama, Kazuoen
dc.contributor.authorMiyazaki, Shuichien
dc.contributor.authorYanagisawa, Hirokien
dc.contributor.alternative岩間, 一雄ja
dc.contributor.alternative宮崎, 修一ja
dc.contributor.alternative柳澤, 弘揮ja
dc.date.accessioned2012-05-09T01:54:50Z-
dc.date.available2012-05-09T01:54:50Z-
dc.date.issued2012-05-
dc.identifier.issn1570-8667-
dc.identifier.urihttp://hdl.handle.net/2433/155464-
dc.description.abstractManlove 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).en
dc.format.mimetypeapplication/pdf-
dc.language.isoeng-
dc.publisherElsevier B.V.en
dc.rights© 2012 Elsevier B.V.en
dc.rightsThis is not the published version. Please cite only the published version.en
dc.rightsこの論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。ja
dc.subjectThe student project allocation problemen
dc.subjectStable matchingen
dc.subjectNP-hardnessen
dc.subjectApproximation algorithmen
dc.subjectApproximation ratioen
dc.titleImproved approximation bounds for the Student-Project Allocation problem with preferences over projectsen
dc.typejournal article-
dc.type.niitypeJournal Article-
dc.identifier.ncidAA11927413-
dc.identifier.jtitleJournal of Discrete Algorithmsen
dc.identifier.volume13-
dc.identifier.spage59-
dc.identifier.epage66-
dc.relation.doi10.1016/j.jda.2012.02.001-
dc.textversionauthor-
dcterms.accessRightsopen access-
Appears in Collections:Journal Articles

Show simple item record

Export to RefWorks


Export Format: 


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