An Eigenvector Structure for a Facilities Location Problem and a Related Algorithm.
Abstract
The special case of the quadratic assignment problem, find a permutation tau of (1,2,...,n) which minimizes the summation from j = 1 to n of c sub (j tau(j)) + (the summation from j = 1) to n)) (the summation from k = 1 to n) (f sub jk) d sub (tau(j) tau(k)) is reformulated in terms of an eigenvector structure derived from the matrices D and F. A related suboptimal algorithm is developed and compared with present algorithms using matrices of size 5, 6, 7, 8, 12, 15, 20, and 30. The new algorithm is most efficient in early iterations, suggesting its usefulness in determining a good starting permutation for other algorithms. Evaluation of any suboptimal algorithm for this problem is considered and a regression line developed to fit least cost for the matrices tried. The relationship between this problem and the Traveling Salesman problem is noted. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 05, 1974
- Accession Number
- AD0783689
Entities
People
- C. Terrence Ireland
Organizations
- George Washington University