Optimal Partial Discretization Orders for Discretizable Distance Geometry

Douglas S. Gonçalves 1 Antonio Mucherino 2
2 MIMETIC - Analysis-Synthesis Approach for Virtual Human Simulation
UR2 - Université de Rennes 2, Inria Rennes – Bretagne Atlantique , IRISA-D6 - MEDIA ET INTERACTIONS
Abstract : The Distance Geometry Problem (DGP) asks whether a simple weighted undirected graph G = (V,E,d) can be embedded in a given space so that the weights of the edges of G, when available, are the same as the distances between pairs of embedded vertices. The DGP can be discretized when some particular assumptions are satisfied, which are strongly dependent on the vertex ordering assigned to G. In this work, we focus on the problem of identifying optimal partial discretization orders for the DGP. The solutions to this problem are in fact vertex orders that allow for the discretization of the DGP. Moreover, these partial orders are optimal in the sense that they optimize, at each rank, a given set of objectives aimed to improve the structure of the search space after the discretization. This ordering problem is tackled from a theoretical point of view, and some practical experiences on sets of artificially generated instances, as well as on real-life instances, are provided.
Type de document :
Article dans une revue
International Transactions in Operational Research, Wiley, 2016, 23 (5), pp.947-967. 〈10.1111/itor.12249〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01402366
Contributeur : Antonio Mucherino <>
Soumis le : jeudi 24 novembre 2016 - 15:46:59
Dernière modification le : mercredi 16 mai 2018 - 11:23:34

Lien texte intégral

Identifiants

Citation

Douglas S. Gonçalves, Antonio Mucherino. Optimal Partial Discretization Orders for Discretizable Distance Geometry. International Transactions in Operational Research, Wiley, 2016, 23 (5), pp.947-967. 〈10.1111/itor.12249〉. 〈hal-01402366〉

Partager

Métriques

Consultations de la notice

477