An Exact Algorithm for Finite Metric Space Embedding into a Euclidean Space When the Dimension of the Space Is Not Known

摘要

We present a O(n~3) algorithm for solving the Distance Geometry Problem for a complete graph (a simple undirected graph in which every pair of distinct vertices is connected by a unique edge) consisting of n +1 vertices and non-negatively weighted edges. It is known that when the solution of the problem exists, the dimension of the Euclidean embedding is at most n. The algorithm provides the smallest possible dimension of the Euclidean space for which the exact embedding of the graph exists. Alternatively, when the distance matrix under consideration is non-Euclidean, the algorithm determines a subset of graph vertices whose mutual distances form the Euclidean matrix. The proposed algorithm is an exact algorithm. If the distance matrix is a Euclidean matrix, the algorithm provides a geometrically unambiguous solution for the location of the graph vertices. The presented embedding method was illustrated using examples of the metric traveling salesman problem that allowed us in some cases to obtain high dimensional partial immersions.