# Algorithms for a Simple Point Placement Problem

## Joshua Redstone and Walter L. Ruzzo

###
Algorithms and Complexity, 4th Italian Conference,
CIAC 2000, Rome, Italy, March 2000, pp. 32-43.

**Abstract: **
We consider algorithms for a simple one-dimensional point
placement problem: given *N* points on a line, and noisy
measurements of the distances between many pairs of them,
estimate the relative positions of the points. Problems of
this flavor arise in a variety of contexts. The particular
motivating example that inspired this work comes from
molecular biology; the points are markers on a chromosome and
the goal is to map their positions. The problem is NP-hard
under reasonable assumptions. We present two algorithms for
computing least squares estimates of the ordering and
positions of the markers: a branch and bound algorithm and a
highly effective heuristic search algorithm. The branch and
bound algorithm is able to solve to optimality problems of 18
markers in about an hour, visiting about 10^6 nodes out of
a search space of 10^16 nodes. The local search algorithm
usually was able to find the global minimum of problems of
similar size in about one second, and should comfortably
handle much larger problem instances.

**Download: **
PostScript
PDF
Conference Proceedings

*
E-mail: ruzzo /at/ cs /dot/ washington /dot/ edu
*