A Study of Three Different Approaches to Point Placement on a Line in an Inexact Model

The point placement problem is to determine the locations of n distinct points on a line uniquely (up to translation and reflection) by making the fewest possible pairwise distance queries of an adversary (an adversary is just a source of true distances). A number of deterministic and randomized algorithms are available when distances are known exactly. In this paper, we discuss the problem in an inexact model. This is when distances returned by the adversary are not exact; instead, only upper and lower bounds on the distances are provided. We explore three different approaches to this problem. The first is based on an adaption of a distance geometry approach that Havel and Crippen [6] used to solve the molecular conformation problem. The second is based on a linear programming solution to a set of difference constraints that was used by Mumey [7] to solve a probe location problem arsing in DNA sequence analysis. The third is based on a heuristic called Stochastic Proximity Embedding, proposed by Agrafiotis [8]. Extensive experiments were carried out to determine the most promising approach vis-a-vis two parameters: run-time and quality of the embedding, measured by computing a certain stress function.