Gilmore-Lawler bound of quadratic assignment problem |
| |
Authors: | Yong Xia |
| |
Institution: | (1) Department of Applied Mathematics; Key Laboratory of Mathematics, Informatics and Behavioral Semantics of the Ministry of Education of China, Beihang University, Beijing, 100083, China |
| |
Abstract: | 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.
|
| |
Keywords: | Quadratic assignment problem (QAP) Gilmore-Lawler bound computational complexity NP-hard |
本文献已被 万方数据 SpringerLink 等数据库收录! |
|