Improved approximation bounds for the Student-Project Allocation problem with preferences over projects

Improved approximation bounds for the Student-Project Allocation problem with preferences over projects
复制标题

改进了学生项目分配问题的近似界限以及对项目的偏好

DOI：
10.1016/j.jda.2012.02.001
复制
发表时间：
2012
期刊：
J. Discrete Algorithms
影响因子：
--
通讯作者：
Hiroki Yanagisawa
Hiroki Yanagisawa
中科院分区：
--
文献类型：
--
作者：
Kazuo Iwama;Shuichi Miyazaki;Hiroki Yanagisawa

文献摘要

相似文献

Manlove和O. Malley（2008）[8]提出了学生项目分配问题（SPA-P）。他们证明了在SPA-P中寻找最大稳定匹配的问题是APX困难的，并给出了多项式时间2-近似算法。本文给出了一个改进的上界为1.5，下界为21/19（>1.1052）。
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).