Optimal partial discretization orders for discretizable distance geometry

The distance geometry problem (DGP) studies 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 a...

Full description

Saved in:
Bibliographic Details
Published in:International transactions in operational research 2016-09, Vol.23 (5), p.947-967
Main Authors: Gonçalves, Douglas S., Mucherino, Antonio
Format: Article
Language:English
Subjects:
Computational Geometry
Computer Science
Discrete Mathematics
Discretization
distance geometry
Geometry
Graph theory
Graphs
multilevel optimization
Operational research
Operations research
Optimization
Order disorder
partial orders
Searching
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The distance geometry problem (DGP) studies 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 paper, 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 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.
ISSN:0969-6016
1475-3995
DOI:10.1111/itor.12249