ERIC Number: EJ720501
Record Type: Journal
Publication Date: 2005-Jun
Reference Count: 31
Optimal Least-Squares Unidimensional Scaling: Improved Branch-and-Bound Procedures and Comparison to Dynamic Programming
Brusco, Michael J.; Stahl, Stephanie
Psychometrika, v70 n2 p253-270 Jun 2005
There are two well-known methods for obtaining a guaranteed globally optimal solution to the problem of least-squares unidimensional scaling of a symmetric dissimilarity matrix: (a) dynamic programming, and (b) branch-and-bound. Dynamic programming is generally more efficient than branch-and-bound, but the former is limited to matrices with approximately 26 or fewer objects because of computer memory limitations. We present some new branch-and-bound procedures that improve computational efficiency, and enable guaranteed globally optimal solutions to be obtained for matrices with up to 35 objects. Experimental tests were conducted to compare the relative performances of the new procedures, a previously published branch-and-bound algorithm, and a dynamic programming solution strategy. These experiments, which included both synthetic and empirical dissimilarity matrices, yielded the following findings: (a) the new branch-and-bound procedures were often drastically more efficient than the previously published branch-and-bound algorithm, (b) when computationally feasible, the dynamic programming approach was more efficient than each of the branch-and-bound procedures, and (c) the new branch-and-bound procedures require minimal computer memory and can provide optimal solutions for matrices that are too large for dynamic programming implementation.
Descriptors: Least Squares Statistics, Comparative Analysis, Programming, Mathematics, Scaling, Psychometrics
Springer, 233 Spring Street, New York, NY 10013. Tel: 212-460-1539; Fax: 212-460-1594.
Publication Type: Journal Articles; Reports - Evaluative
Education Level: N/A
Authoring Institution: N/A