Article ID: | iaor20117110 |
Volume: | 8 |
Issue: | 3 |
Start Page Number: | 446 |
End Page Number: | 451 |
Publication Date: | Aug 2011 |
Journal: | Discrete Optimization |
Authors: | Tansel Barbaros, Erdoan Gne |
Keywords: | polynomial programs, quadratic assignment |
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.