Special Cases of the Quadratic Assignment Problem

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1976
Accession Number
ADA025605

Entities

People

  • M. Gerrard
  • Nicos Christofides

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Algorithms
  • Assembly
  • Assembly Lines
  • Computations
  • Computer Programming
  • Computers
  • Dynamic Programming
  • Electronic Components
  • Graph Theory
  • Heuristic Methods
  • Magnetic Tape
  • Military Research
  • Polynomials
  • Scheduling (Production)
  • Sequences
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research