论文标题
从未标记的欧几里得长度的一个维度重建
Reconstruction in one dimension from unlabeled Euclidean lengths
论文作者
论文摘要
让$ g $为$ 3 $连接的有序图，带有$ n $顶点和$ m $边缘。令$ \ mathbf {p} $为这些$ n $顶点的随机选择映射到整数范围$ \ {1，2,3，\ ldots，2^b \} $ for $ b \ ge m^2 $。令$ \ ell $为$ m $ euclidean长度的向量，$ g $的边缘在$ \ mathbf {p} $下方。在本文中，我们表明，如果超过$ \ Mathbf {p} $，我们可以从$ \ ell $中有效地重建$ g $和$ g $ g $和$ \ mathbf {p} $。在最坏的情况下，即使给出了$ g $和$ \ ell $，这种重建问题也是NP-HARD。我们还表明，我们的结果处于$ \ ell $中少量错误的情况下，并且在实际环境中具有足够准确的长度测量。 我们的方法结合了晶格还原，该晶格降低以前已用于解决随机子集总和问题，并与Seymour的算法相结合，可以有效地重建有序的图表，以给定其Matroid的独立性。
Let $G$ be a $3$-connected ordered graph with $n$ vertices and $m$ edges. Let $\mathbf{p}$ be a randomly chosen mapping of these $n$ vertices to the integer range $\{1, 2,3, \ldots, 2^b\}$ for $b\ge m^2$. Let $\ell$ be the vector of $m$ Euclidean lengths of $G$'s edges under $\mathbf{p}$. In this paper, we show that, with high probability over $\mathbf{p}$, we can efficiently reconstruct both $G$ and $\mathbf{p}$ from $\ell$. This reconstruction problem is NP-HARD in the worst case, even if both $G$ and $\ell$ are given. We also show that our results stand in the presence of small amounts of error in $\ell$, and in the real setting, with sufficiently accurate length measurements. Our method combines lattice reduction, which has previously been used to solve random subset sum problems, with an algorithm of Seymour that can efficiently reconstruct an ordered graph given an independence oracle for its matroid.
