On the Exact Solution of the Distance Geometry with Interval Distances in Dimension 1

Antonio Mucherino 1
1 MIMETIC - Analysis-Synthesis Approach for Virtual Human Simulation
UR2 - Université de Rennes 2, Inria Rennes – Bretagne Atlantique , IRISA-D6 - MEDIA ET INTERACTIONS
Abstract : Distance Geometry consists in embedding a simple weighted undirected graph in a given space so that the distances between embedded vertices correspond to the edge weights. Weights can be either exact real values, or real-valued intervals. In this work, the focus is on problems where the embedding space is the Euclidean 1-dimensional space, and the general situation where distances can be represented by intervals is taken into consideration. A previously proposed branch-and-prune algorithm is adapted to the 1-dimensional case, and the proposed variant turns out to be deterministic even in presence of interval distances. Backtracking pruning is introduced in the algorithm for guaranteeing that all vertex positions in a given solution are actually feasible. The proposed algorithm is tested on a set of artificially generated instances in dimension 1.
Complete list of metadatas

https://hal.inria.fr/hal-01826209
Contributor : Antonio Mucherino <>
Submitted on : Friday, June 29, 2018 - 10:36:28 AM
Last modification on : Friday, September 13, 2019 - 9:48:07 AM

Identifiers

Citation

Antonio Mucherino. On the Exact Solution of the Distance Geometry with Interval Distances in Dimension 1. Stefka Fidanova. Recent Advances in Computational Optimization, 717, Springer, pp.123-134, 2018, Studies in Computational Intelligence, ⟨10.1007/978-3-319-59861-1_8⟩. ⟨hal-01826209⟩

Share

Metrics

Record views

301