
As an Amazon Associate and affiliate partner, Menrva Books earns from qualifying purchases. Learn more
The quadratic assignment problem (QAP) is a classical combinatorial optimization problem with numerous applications in facility location, scheduling, manufacturing, VLSI design, statistical data analysis, etc. The QAP is an extremely hard problem from both theoretical and practical points of view: 1) The QAP is NP-hard to solve to optimality and to approximate within a constant approximation ratio, and 2) QAP instances of size larger than 22 are still considered intractable. Hence, the QAP is in effect a problem that has yet to be solved. This volume presents a general overview of the most studied aspects of the QAP, as well as outlining a number of research directions which currently seem to be promising. The book gives a systematic presentation of various results scattered in the literature, such as: bounding techniques and exact solution methods, linearisations, heuristic approaches and computational complexity. Some more recent research directions discussed in detail in the book are the asymptotic behaviour of the QAP and restricted versions of the problem: in particular, polynomially solvable and provably hard cases of the QAP. Audience: This volume will be of interest to researchers and students interested in the quadratic assignment problem and to practitioners who face the QAP and wish to better understand this problem in its inherent complexity.
The Quadratic Assignment Problem (QAP) presents a formidable challenge in combinatorial optimization, with significant implications across various fields. This volume offers a comprehensive overview of the QAP, detailing its NP-hard nature, the intractability of larger instances, and the ongoing quest for optimal solutions. It systematically compiles scattered literature on bounding techniques, exact solution methods, linearizations, heuristic approaches, and computational complexity, while also exploring recent research into asymptotic behavior and specific polynomially solvable or provably hard cases.
This volume is of interest to researchers and students focused on the Quadratic Assignment Problem, as well as practitioners grappling with its complexities. It aims to provide a deeper understanding of the problem's inherent difficulty and to outline promising avenues for future research. The book synthesizes existing knowledge and highlights current challenges in solving QAP instances.
Page Count:
287
Publication Date:
1998-01-01
ISBN-10:
1441947868
ISBN-13:
9781441947864
No comments yet. Be the first to share your thoughts!