The Euclidean distance geometry problem (EDGP) includes locating sensors in a sensor network and constructing a molecular configuration using given distances in the two or three-dimensional Euclidean space. When the locations of some nodes, called anchors, are given, the problem can be dealt with many existing methods. An anchor-free problem in the three-dimensional space, however, is a more challenging problem and can be handled with only a few methods. We propose an efficient and robust numerical method for large-scale EDGPs with exact and corrupted distances including anchor-free three-dimensional problems. The method is based on successive application of the sparse version of full semidefinite programming relaxation (SFSDP) proposed by Kim, Kojima, Waki and Yamashita, and can be executed in parallel. Numerical results on large-scale anchor-free three-dimensional problems with more than 10000 nodes demonstrate that the proposed method performs better than the direct application of SFSDP and the divide and conquer method of Leung and Toh in terms of efficiency and/or effectiveness measured in the root mean squared distance.
Citation
Research report, B-470, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152-8552 Japan.