Special Cases of the Quadratic Assignment Problem

reportActive / Technical Report | Accession Number: ADA025605 | Open PDF

Abstract:

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.

Author(s):
Christofides, Nicos ; Gerrard, M.
Author Organization(s):
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Descriptive Note:
Research rept.
Supplementary Note:
Sponsored in part by Office of Naval Research, Arlington, Va. Prepared in cooperation with Imperial Coll. of Science and Technology, London (England). DOI: 10.21236/ADA025605
Pagination:
0024

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release, Document Partially Illegible
Distribution Statement:
Approved For Public Release; Distribution Is Unlimited. Document Partially Illegible.

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
RR-391, WP-69-75-76
Monitor Series:
ONR
 Subject Terms
Joint Capability Areas:
JCA_1.2_Force Preparation; JCA_1_Force Support; JCA_1.2.3_Educating; JCA_6_Net Centric; JCA_6.2.1_Information Sharing; JCA_6.2.2_Computing Services; JCA_6.4.1_Secure Information Exchange
Communities of Interest:
Advanced Electronics
Descriptor(s):
*DYNAMIC PROGRAMMING, ALGORITHMS, NETWORK FLOWS, SCHEDULING
Field(s)/Group(s):
Operations Research
Keyword(s):
GRAPH THEORY, *QUADRATIC ASSIGNMENT PROBLEM, TRAVELING SALESMAN PROBLEM, LAYOUT PROBLEMS, LOCATION PROBLEMS
Report Date:
1976 Apr 01