کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430581 | 688051 | 2012 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Improved approximation bounds for the Student-Project Allocation problem with preferences over projects
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: 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](/preview/png/430581.png)
چکیده انگلیسی
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).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 13, May 2012, Pages 59–66
Journal: Journal of Discrete Algorithms - Volume 13, May 2012, Pages 59–66
نویسندگان
Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa,