Two classes of Quadratic Assignment Problems that are solvable as Linear Assignment Problems

Two classes of Quadratic Assignment Problems that are solvable as Linear Assignment Problems

0.00 Avg rating0 Votes
Article ID: iaor20117110
Volume: 8
Issue: 3
Start Page Number: 446
End Page Number: 451
Publication Date: Aug 2011
Journal: Discrete Optimization
Authors: ,
Keywords: polynomial programs, quadratic assignment
Abstract:

The Quadratic Assignment Problem is one of the hardest combinatorial optimization problems known. We present two new classes of instances of the Quadratic Assignment Problem that can be reduced to the Linear Assignment Problem and give polynomial time procedures to check whether or not an instance is an element of these classes.

Reviews

Required fields are marked *. Your email address will not be published.