TY - JOUR
T1 - Gilmore-Lawler bound of quadratic assignment problem
AU - Xia, Yong
PY - 2008/2
Y1 - 2008/2
N2 - The Gilmore-Lawler bound (GLB) is one of the well-known lower bound of quadratic assignment problem (QAP). Checking whether GLB is tight is an NP-complete problem. In this article, based on Xia and Yuan linearization technique, we provide an upper bound of the complexity of this problem, which makes it pseudo-polynomial solvable. We also pseudopolynomially solve a class of QAP whose GLB is equal to the optimal objective function value, which was shown to remain NP-hard.
AB - The Gilmore-Lawler bound (GLB) is one of the well-known lower bound of quadratic assignment problem (QAP). Checking whether GLB is tight is an NP-complete problem. In this article, based on Xia and Yuan linearization technique, we provide an upper bound of the complexity of this problem, which makes it pseudo-polynomial solvable. We also pseudopolynomially solve a class of QAP whose GLB is equal to the optimal objective function value, which was shown to remain NP-hard.
KW - Computational complexity
KW - Gilmore-Lawler bound
KW - NP-hard
KW - Quadratic assignment problem (QAP)
UR - https://www.scopus.com/pages/publications/38349111661
U2 - 10.1007/s11464-008-0010-4
DO - 10.1007/s11464-008-0010-4
M3 - 文章
AN - SCOPUS:38349111661
SN - 1673-3452
VL - 3
SP - 109
EP - 118
JO - Frontiers of Mathematics in China
JF - Frontiers of Mathematics in China
IS - 1
ER -