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

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
نویسندگان
, ,