Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430581 | Journal of Discrete Algorithms | 2012 | 8 Pages |
Abstract
Manlove and OʼMalley (2008) [8] 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)(>1.1052).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa,