Affordable Access

Publisher Website

A Graph Theoretic Analysis of Bounds for the Quadratic Assignment Problem

DOI: 10.1016/s0304-0208(08)73458-3


We express the Quadratic Assignment Problem in terms of graph multiplication of a flow graph Gf with a distance graph Gd. By decomposing Gf into simpler graphs, we give a general unified procedure to calculate bounds. This procedure generates the two previously known bounds as special cases and also generates some new bounds. By enumerating all practical decompositions, we show that no better bounds can be computed in reasonable time—by solving linear assignment subproblems—other than the bounds pointed out in this paper.

There are no comments yet on this publication. Be the first to share your thoughts.