کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420394 | 683930 | 2009 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Optimal popular matchings
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper we consider the problem of computing an “optimal” popular matching. We assume that our input instance G=(A∪P,E1∪̇⋯∪̇Er) admits a popular matching and here we are asked to return not any popular matching but an optimal popular matching, where the definition of optimality is given as a part of the problem statement; for instance, optimality could be fairness in which case we are required to return a fair popular matching. We show an O(n2+m)O(n2+m) algorithm for this problem, assuming that the preference lists are strict, where mm is the number of edges in GG and nn is the number of applicants.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 14, 28 July 2009, Pages 3181–3186
Journal: Discrete Applied Mathematics - Volume 157, Issue 14, 28 July 2009, Pages 3181–3186
نویسندگان
Telikepalli Kavitha, Meghana Nasre,