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

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

Onderzoeksoutput: Boek/rapportRapportAcademic

84 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 respectively NP-hard.
Originele taal-2Engels
Uitgeverijs.n.
Aantal pagina's16
StatusGepubliceerd - 2014

Publicatie series

NaamarXiv
Volume1402.3500 [math.OC]

Vingerafdruk Duik in de onderzoeksthema's van 'Well-solvable cases of the QAP with block-structured matrices'. Samen vormen ze een unieke vingerafdruk.

Citeer dit