Special Cases of the Quadratic Assignment Problem
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
By considering the quadratic assignment problem QAP as that of minimizing the product of a distance-graph with a flow-graph several special cases of the QAP are investigated. A polynomial-growth algorithm is described for the QAP when the distance and flow-graphs are isomorphic trees. In the case when the graphs are single stars the algorithm becomes the well known rule for multiplying two sequences of numbers. The case of a complete distance-graph and a tree flow-graph becomes the travelling salesman problem when the tree is a hamiltonian chain and the flows are all unity. A dynamic programming algorithm is presented for the case of the flow-graph being a general tree with arbitrary flows. The very special case of narrow bipartite graphs is also considered.
- Operations Research