Gilmore-Lawler bound of quadratic assignment problem

Yong Xia

doi:10.1007/s11464-008-0010-4

Gilmore-Lawler bound of quadratic assignment problem

Yong Xia^*

^*Corresponding author for this work

School of Mathematical Sciences

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

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.

Original language	English
Pages (from-to)	109-118
Number of pages	10
Journal	Frontiers of Mathematics in China
Volume	3
Issue number	1
DOIs	https://doi.org/10.1007/s11464-008-0010-4
State	Published - Feb 2008

Keywords

Computational complexity
Gilmore-Lawler bound
NP-hard
Quadratic assignment problem (QAP)

Access to Document

10.1007/s11464-008-0010-4

Cite this

@article{7fefc5e68b8e4ca5a8876eda9f89458c,

title = "Gilmore-Lawler bound of quadratic assignment problem",

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 = "Computational complexity, Gilmore-Lawler bound, NP-hard, Quadratic assignment problem (QAP)",

author = "Yong Xia",

year = "2008",

month = feb,

doi = "10.1007/s11464-008-0010-4",

language = "英语",

volume = "3",

pages = "109--118",

journal = "Frontiers of Mathematics in China",

issn = "1673-3452",

publisher = "Higher Education Press Limited Company",

number = "1",

}

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 -

Gilmore-Lawler bound of quadratic assignment problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this