Change search
ReferencesLink to record
Permanent link

Direct link
Fitting points on the real line and its application to RH mapping
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2003 (English)In: Journal of Algorithms, ISSN 0196-6774, E-ISSN 1090-2678, Vol. 49, no 1, 42-62 p.Article in journal (Refereed) Published
Abstract [en]

A natural problem is that of, given an n x 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. We refer to the variation in which the difference in distance is measured in maximum norm as the MATRIX-TO-LINE problem. The MATRIX-TO-LINE problem has previously been shown to be NP-complete [J.B. Saxe, 17th Allerton Conference in Communication, Control, and Computing, 1979, pp. 480-489]. We show that it can be approximated within 2, but unless P = NP not within 7/5 - delta for any delta > 0. We also show a tight lower bound under a stronger assumption. We show that the MATRIX-TO-LINE problem cannot be approximated within 2 - delta unless 3-colorable graphs can be colored with [4/delta] colors in polynomial time. Currently, the best polynomial time algorithm colors a 3-colorable graph with (O) over tilde (n(3/14)) colors [A. Blum, D. Karger, Inform. Process. Lett. 61 (1), (1997), 49-53]. We apply our MATRIX-TO-LINE algorithm to a problem in computational biology, namely, the Radiation Hybrid (RH) problem. That is, 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.

Place, publisher, year, edition, pages
2003. Vol. 49, no 1, 42-62 p.
Keyword [en]
line fitting, RH mapping, approximation, lower bounds, graphs
URN: urn:nbn:se:kth:diva-22909DOI: 10.1016/s0196-6774(03)00083-xISI: 000186142500004OAI: diva2:341607
QC 20100525Available from: 2010-08-10 Created: 2010-08-10Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Håstad, JohanLagergren, Jens
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Journal of Algorithms

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 26 hits
ReferencesLink to record
Permanent link

Direct link