Fitting Points on the Real Line and Its Application to RH Mapping

Johan Håstad, Lars Ivansson, Jens Lagergren

Abstract

The Matrix-To-Line problem is that of, given an n × n symmetric matrix D, finding an arrangement of n points on the real line such that the so obtained distances agree as well as possible with the by D specified distances, w.r.t. the max-norm. The Matrix-To-Line problem has previously been shown to be NP-complete [11]. We show that it can be approximated within 2, but not within 4/3 unless P=NP. We also show tight bounds under a stronger assumption. We show that the Matrix-To-Line problem cannot be approximated within 2 − δ unless 3-colorable graphs can be colored with ⌈4/δ⌉ colors in polynomial time. Currently, the best polynomial time algorithm colors a 3-colorable graph with Õ(n 3/14) colors [4]. We apply our Matrix-To-Line algorithm to a problem in computational biology, namely, the Radiation Hybrid (RH) problem, i.e., the algorithmic part of a physical mapping method called RH mapping. This gives us the first algorithm with a guaranteed convergence for the general RH problem.
BibTeX
@inproceedings{hastad1998fitting,
  author = {Johan Håstad and Lars Ivansson and Jens Lagergren},
  title = {{Fitting Points on the Real Line and Its Application to RH Mapping}},
  booktitle = {ESA},
  year = {1998},
  doi = {10.1007/3-540-68530-8\_39},
}

Loading related content...

Figure