کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6894938 | 1445934 | 2018 | 40 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
New special cases of the Quadratic Assignment Problem with diagonally structured coefficient matrices
ترجمه فارسی عنوان
موارد خاص جدیدی از مسئله تخصیص درجه دوم با ماتریس ضریب ساختاری مورب
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بهینه سازی ترکیبی، تخصیص مجدد، رابینسونین، ماتریس مونج، ماتریکس کلمنسون،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We consider new polynomially solvable cases of the well-known Quadratic Assignment Problem involving coefficient matrices with a special diagonal structure. By combining the new special cases with polynomially solvable special cases known in the literature we obtain a new and larger class of polynomially solvable special cases of the QAP where one of the two coefficient matrices involved is a Robinson matrix with an additional structural property: this matrix can be represented as a conic combination of cut matrices in a certain normal form. The other matrix is a conic combination of a monotone anti-Monge matrix and a down-benevolent Toeplitz matrix. We consider the recognition problem for the special class of Robinson matrices mentioned above and show that it can be solved in polynomial time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 267, Issue 3, 16 June 2018, Pages 818-834
Journal: European Journal of Operational Research - Volume 267, Issue 3, 16 June 2018, Pages 818-834
نویسندگان
Eranda Ãela, Vladimir Deineko, Gerhard J. Woeginger,