A least-squares approach for discretizable distance geometry problems with inexact distances

A branch-and-prune (BP) algorithm is presented for the discretizable distance geometry problem in RK\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}^K$$\end{document} with inexact distances. The algorithm consists in a sequential buildup procedure where possible positions for each new point to be localized are computed by using distances to at least K previously placed reference points and solving a system of quadratic equations. Such a system is solved in a least-squares sense, by finding the best positive semidefinite rank K approximation for an induced Gram matrix. When only K references are available, a second candidate position is obtained by reflecting the least-squares solution through the hyperplane defined by the reference points. This leads to a search tree which is explored by BP, where infeasible branches are pruned on the basis of Schoenberg’s theorem. In order to study the influence of the noise level, numerical results on some instances with distances perturbed by a small additive noise are presented.