
The Library
Linearizable special cases of the QAP
Tools
Çela, Eranda, Deineko, Vladimir G. and Woeginger, Gerhard J. (2016) Linearizable special cases of the QAP. Journal of Combinatorial Optimization, 31 (3). pp. 1269-1279. doi:10.1007/s10878-014-9821-2 ISSN 1382-6905.
|
PDF
WRAP_Deineko_1409.6510v1.pdf - Accepted Version - Requires a PDF viewer. Download (397Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s10878-014-9821-2
Abstract
We consider special cases of the quadratic assignment problem (QAP) that are linearizable in the sense of Bookhold. We provide combinatorial characterizations of the linearizable instances of the weighted feedback arc set QAP, and of the linearizable instances of the traveling salesman QAP. As a by-product, this yields a new well-solvable special case of the weighted feedback arc set problem.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Alternative Title: | |||||||||
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||||||
Library of Congress Subject Headings (LCSH): | Quadratic assignment problem, Combinatorial optimization | ||||||||
Journal or Publication Title: | Journal of Combinatorial Optimization | ||||||||
Publisher: | Springer New York LLC | ||||||||
ISSN: | 1382-6905 | ||||||||
Official Date: | April 2016 | ||||||||
Dates: |
|
||||||||
Volume: | 31 | ||||||||
Number: | 3 | ||||||||
Number of Pages: | 11 | ||||||||
Page Range: | pp. 1269-1279 | ||||||||
DOI: | 10.1007/s10878-014-9821-2 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 25 January 2016 | ||||||||
Date of first compliant Open Access: | 26 January 2016 | ||||||||
Funder: | Fonds zur Förderung der Wissenschaftlichen Forschung (Austria) (FWF), University of Warwick. Centre for Discrete Mathematics and Its Applications, Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Netherlands Organisation for Scientific Research] (NWO) |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year