Ç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

Preview

PDF WRAP_Deineko_1409.6510v1.pdf - Accepted Version - Requires a PDF viewer. Download (397Kb) | Preview

Request Changes to record.

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:	Date Event April 2016 Published 24 December 2014 Available 24 November 2014 Accepted
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
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