Consider an experiment which measures the distances between points in a point set. Further consider that the experiment only finds distances but not only the underlying graph. That is, the endpoints of each distance are not given. This is the unassigned distance geometry (UDG) problem, where both the underlying graph and the embedding must be found. In terms of the matrix completion problem, we are given the values of some of the elements in the matrix but we do not know where to place these elements in the matrix. In the UDG problem the input is simple, we are given a list of distances and the challenge is to find the structure from which these distances are derived. Sensor location problems and nano-structure problems are two examples of applications. This talk will introduce and discuss: the UDG problem; the concept of generic distance lists; proof that algorithms for UDG problems with precise generic complete distance lists are in the polynomial class; and describe new heuristics to solve UDG problems using continuous optimization methods.

INTRODUCTIONS ARE AT:
The unassigned distance geometry problem
P.M.Duxbury, L.Granlund, S.R.Gujarathi, P.Juhas, S.J.L.Billinge. Discrete Applied Mathematics
Volume 204, 11 May 2016, Pages 117-132.
Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures
S.J.L. Billinge, P.M. Duxbury, D.S. Gonçalves, C. Lavor, A. Mucherino. Annals of Operations Research 271 (1), 161-203