کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418916 681727 2015 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Well-solvable cases of the QAP with block-structured matrices
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Well-solvable cases of the QAP with block-structured matrices
چکیده انگلیسی

We investigate special cases of the quadratic assignment problem (QAP) where one of the two underlying matrices carries a simple block structure. For the special case where the second underlying matrix is a monotone anti-Monge matrix, we derive a polynomial time result for a certain class of cut problems. For the special case where the second underlying matrix is a product matrix, we identify two sets of conditions on the block structure that make this QAP polynomially solvable and NP-hard, respectively.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 186, 11 May 2015, Pages 56–65
نویسندگان
, , ,