Downloads: 477
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
j.jda.2012.02.001.pdf | 141.34 kB | Adobe PDF | View/Open |
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Iwama, Kazuo | en |
dc.contributor.author | Miyazaki, Shuichi | en |
dc.contributor.author | Yanagisawa, Hiroki | en |
dc.contributor.alternative | 岩間, 一雄 | ja |
dc.contributor.alternative | 宮崎, 修一 | ja |
dc.contributor.alternative | 柳澤, 弘揮 | ja |
dc.date.accessioned | 2012-05-09T01:54:50Z | - |
dc.date.available | 2012-05-09T01:54:50Z | - |
dc.date.issued | 2012-05 | - |
dc.identifier.issn | 1570-8667 | - |
dc.identifier.uri | http://hdl.handle.net/2433/155464 | - |
dc.description.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). | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Elsevier B.V. | en |
dc.rights | © 2012 Elsevier B.V. | en |
dc.rights | This is not the published version. Please cite only the published version. | en |
dc.rights | この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 | ja |
dc.subject | The student project allocation problem | en |
dc.subject | Stable matching | en |
dc.subject | NP-hardness | en |
dc.subject | Approximation algorithm | en |
dc.subject | Approximation ratio | en |
dc.title | Improved approximation bounds for the Student-Project Allocation problem with preferences over projects | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.ncid | AA11927413 | - |
dc.identifier.jtitle | Journal of Discrete Algorithms | en |
dc.identifier.volume | 13 | - |
dc.identifier.spage | 59 | - |
dc.identifier.epage | 66 | - |
dc.relation.doi | 10.1016/j.jda.2012.02.001 | - |
dc.textversion | author | - |
dcterms.accessRights | open access | - |
Appears in Collections: | Journal Articles |

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