Consider the problem of determining whether or not a partial dissimilarity
matrix can be completed to a Euclidean distance matrix. The dimension of th
e distance matrix may be restricted and the known dissimilarities may be pe
rmitted to vary subject to bound constraints. This problem can be formulate
d as an optimization problem for which the global minimum is zero if and on
ly if completion is possible. The optimization problem is derived in a very
natural way from an embedding theorem in classical distance geometry and f
rom the classical approach to multidimensional scaling. It belongs to a gen
eral family of problems studied by Trosset (Technical Report 97-3, Departme
nt of Computational & Applied Mathematics-MS 134, Rice University, Houston,
TX 77005-1892, 1997) and can be formulated as a nonlinear programming prob
lem with simple bound constraints. Thus, this approach provides a construct
ive technique for obtaining approximate solutions to a general class of dis
tance matrix completion problems.