An r-Dimensional Quadratic Placement Algorithm
Kenneth M. Hall · Management Science · 1970
In this paper the solution to the problem of placing n connected points (or nodes) in r-dimensional Euclidean space is given. The criterion for optimality is minimizing a weighted sum of squared distances between the points subject to quadratic constraints of the form X′X = 1, for each of the r unknown coordinate vectors. It is proved that the problem reduces to the minimization of a sum or r positive semi-definite quadratic forms which, under the quadratic constraints, reduces to the problem of finding r eigenvectors of a special “disconnection” matrix. It is shown, by example, how this can serve as a basis for cluster identification.
Cited by 522 works. doi:10.1287/mnsc.17.3.219
Authors
References
- The Backboard Wiring Problem: A Placement Algorithm
- The Quadratic Assignment Problem
- Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
- A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities
- Quadratic Assignment Problem Algorithms and the Location of Indivisible Facilities
- An Algorithm for the Quadratic Assignment Problem