کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142307 | 957140 | 2015 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure](/preview/png/1142307.png)
چکیده انگلیسی
We present a new polynomially solvable case of the Quadratic Assignment Problem in Koopmans–Beckman form QAP(A,B), by showing that the identity permutation is optimal when AA and BB are respectively a Robinson similarity and dissimilarity matrix and one of AA or BB is a Toeplitz matrix. A Robinson (dis)similarity matrix is a symmetric matrix whose entries (increase) decrease monotonically along rows and columns when moving away from the diagonal, and such matrices arise in the classical seriation problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 43, Issue 1, January 2015, Pages 103–109
Journal: Operations Research Letters - Volume 43, Issue 1, January 2015, Pages 103–109
نویسندگان
M. Laurent, M. Seminaroti,