Well-solvable cases of the QAP with block-structured matrices

E. Çela; V.G. Deineko; G.J. Woeginger

doi:10.1016/j.dam.2015.01.005

Well-solvable cases of the QAP with block-structured matrices

E. Çela
, V.G. Deineko
, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

14 Citaten (Scopus)

1 Downloads (Pure)

Samenvatting

We investigate special cases of the quadratic assignment problem (QAP) where one of the two underlying matrices carries a simple block structure. For the special case where the second underlying matrix is a monotone anti-Monge matrix, we derive a polynomial time result for a certain class of cut problems. For the special case where the second underlying matrix is a product matrix, we identify two sets of conditions on the block structure that make this QAP polynomially solvable and NP-hard, respectively. Keywords: Combinatorial optimization; Computational complexity; Cut problem; Balanced cut; Monge condition; Product matrix

Originele taal-2	Engels
Pagina's (van-tot)	56-65
Aantal pagina's	10
Tijdschrift	Discrete Applied Mathematics
Volume	186
DOI's	https://doi.org/10.1016/j.dam.2015.01.005
Status	Gepubliceerd - 2015

Toegang tot document

10.1016/j.dam.2015.01.005

Citeer dit

@article{d69a71b837a64b48bee2c05042399c8e,

title = "Well-solvable cases of the QAP with block-structured matrices",

abstract = "We investigate special cases of the quadratic assignment problem (QAP) where one of the two underlying matrices carries a simple block structure. For the special case where the second underlying matrix is a monotone anti-Monge matrix, we derive a polynomial time result for a certain class of cut problems. For the special case where the second underlying matrix is a product matrix, we identify two sets of conditions on the block structure that make this QAP polynomially solvable and NP-hard, respectively. Keywords: Combinatorial optimization; Computational complexity; Cut problem; Balanced cut; Monge condition; Product matrix",

author = "E. {\c C}ela and V.G. Deineko and G.J. Woeginger",

year = "2015",

doi = "10.1016/j.dam.2015.01.005",

language = "English",

volume = "186",

pages = "56--65",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Well-solvable cases of the QAP with block-structured matrices

AU - Çela, E.

AU - Deineko, V.G.

AU - Woeginger, G.J.

PY - 2015

Y1 - 2015

N2 - We investigate special cases of the quadratic assignment problem (QAP) where one of the two underlying matrices carries a simple block structure. For the special case where the second underlying matrix is a monotone anti-Monge matrix, we derive a polynomial time result for a certain class of cut problems. For the special case where the second underlying matrix is a product matrix, we identify two sets of conditions on the block structure that make this QAP polynomially solvable and NP-hard, respectively. Keywords: Combinatorial optimization; Computational complexity; Cut problem; Balanced cut; Monge condition; Product matrix

AB - We investigate special cases of the quadratic assignment problem (QAP) where one of the two underlying matrices carries a simple block structure. For the special case where the second underlying matrix is a monotone anti-Monge matrix, we derive a polynomial time result for a certain class of cut problems. For the special case where the second underlying matrix is a product matrix, we identify two sets of conditions on the block structure that make this QAP polynomially solvable and NP-hard, respectively. Keywords: Combinatorial optimization; Computational complexity; Cut problem; Balanced cut; Monge condition; Product matrix

U2 - 10.1016/j.dam.2015.01.005

DO - 10.1016/j.dam.2015.01.005

M3 - Article

SN - 0166-218X

VL - 186

SP - 56

EP - 65

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Well-solvable cases of the QAP with block-structured matrices

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit