Distance Geometry in Linearizable Norms

International audienceDistance Geometry puts the concept of distance at its center. The basic problem in distance geometry could be described as drawing an edge-weighted undirected graph in R K for some given K such that the positions for adjacent vertices have distance which is equal to the corresponding edge weight. As we are unaware of any work in this field using any other norm but 2, we move some first steps using the 1 and ∞ norms: we discuss worst-case complexity, propose mixed-integer linear programming formulations, and sketch a few heuristic ideas