Fitting Points on the Real Line and Its Application to RH Mapping
Fitting Points on the Real Line and Its Application to RH Mapping
复制标题
实线上的拟合点及其在RH测绘中的应用
DOI：
10.1007/3-540-68530-8_39
复制
发表时间：
1998
影响因子：
1.7
通讯作者：
J. Lagergren
中科院分区：
文献类型：
--
作者：
J. Håstad;Lars Ivansson;J. Lagergren
MATRIX-TO-LINE 问题是，给定一个 n × n 对称矩阵 D，找到实线上 n 个点的排列，使得如此获得的距离尽可能与 D 指定的距离一致。最大范数。 MATRIX-TO-LINE 问题先前已被证明是 NP 完全问题 [11]。我们证明它可以在 2 内近似，但不能在 4=3 内近似，除非 P=NP。我们还在更强的假设下显示了严格的界限。我们证明了 MATRIX-TO-LINE 问题不能在 2 - δ 范围内近似，除非 3 可着色图可以在多项式时间内用 ⌊4/δ⌋ 颜色着色。目前，最好的多项式时间算法使用 O(n3/14) 种颜色对 3 色图进行着色 [4]。
我们将 MATRIX-TO-LINE 算法应用于计算生物学中的一个问题，即辐射混合 (RH) 问题，即称为 RH 映射的物理映射方法的算法部分。这为我们提供了第一个能够保证一般 RH 问题收敛的算法。
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 O(n3/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.