کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871873 | 681668 | 2016 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The assignment problem with nearly Monge arrays and incompatible partner indices
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we study the d-dimensional assignment problem in which entries of the cost array satisfy the Monge property, except for â-entries, which may violate it. We assume that the â-entries are incurred by incompatible partner indices and their number is bounded by an upper bound λ for each index. We show that the problem can be solved in linear time for fixed d and λ, and it becomes strongly NP-hard if d or λ is part of the input.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 211, 1 October 2016, Pages 183-203
Journal: Discrete Applied Mathematics - Volume 211, 1 October 2016, Pages 183-203
نویسندگان
C. WeiÃ, S. Knust, N.V. Shakhlevich, S. Waldherr,