کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
7543507 | 1489494 | 2016 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Stable Marriage and Roommates problems with restricted edges: Complexity and approximability
ترجمه فارسی عنوان
مشکلات زناشویی و هم اتاقی با محدودیت های لبه: پیچیدگی و تقریب پذیری
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
چکیده انگلیسی
Our main theorems prove that for the (bipartite) Stable Marriage problem, case (1) leads to NP-hardness and inapproximability results, whilst case (2) can be solved in polynomial time. For non-bipartite Stable Roommates instances, case (2) yields an NP-hard but (under some cardinality assumptions) 2-approximable problem. In the case of NP-hard problems, we also discuss polynomially solvable special cases, arising from restrictions on the lengths of the preference lists, or upper bounds on the numbers of restricted pairs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 20, May 2016, Pages 62-89
Journal: Discrete Optimization - Volume 20, May 2016, Pages 62-89
نویسندگان
Ágnes Cseh, David F. Manlove,