<p>Paul Lemke Steven S. Skiena Warren D. Smith, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.6172" rel="nofollow">Reconstructing Sets From Interpoint Distances</a>, gave backtracking algorithm that runs in time $O(n^n \log n)$ for the beltway reconstruction problem. As far as I know, this is the best known. The exact complexity of the problem is not known. It is not known to be in $P$ and neither known to be $NP$-complete.</p>

CC BY-SA 3.0
2013-07-09T07:19:49.563Z
Thanks. I've read these two papers: Reconstruction of Integers from Pairwise Distances & Reconstructing Sets From Interpoint Distances. Do you know any other references?
Mahdi Khosravi
CC BY-SA 3.0
2013-07-09T07:24:01.413Z
No. I am not aware of any more recent references.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-07-09T07:08:39.043Z
2013-07-09T07:16:21.173Z
2013-07-09T07:16:21.173Z
Mohammad Al-Turkistany
<p>I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem? <br>
<strong>Beltway Reconstruction Problem</strong>: <br>
Assume there is a set of non-identical integers between 0 and N, we only have pairwise distances of points of that set mod N, How can we reconstruct the original set using this?</p>

CC BY-SA 3.0
2013-07-09T05:17:34.487Z
It's not quite the same problem, but some of the suggestions at http://cstheory.stackexchange.com/questions/17307/how-to-obtain-the-unknown-values-a-i-b-j-given-an-unordered-list-of-a-i-b-j-m?rq=1 look helpful.
David Eppstein
CC BY-SA 3.0
2013-07-09T08:37:39.427Z
[simultaneously cross-posted](http://mathoverflow.net/questions/136156/what-algorithms-do-you-know-for-beltway-reconstruction) on MO.
Kaveh
CC BY-SA 3.0
2013-07-09T08:38:39.710Z
Our [site policy](http://meta.cstheory.stackexchange.com/a/231/) prohibits ***simultaneous*** **crossposting**: it duplicates effort and fractures discussion. Crossposting is permitted after a week has passed without a satisfying answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link to the copies in both directions.
Kaveh
CC BY-SA 3.0
2013-07-09T08:56:03.450Z
I wasn't aware of this rule. Now what should I do?
Mahdi Khosravi
<ds.algorithms><nt.number-theory><comp-number-theory>
What algorithms do you know for beltway reconstruction?
Mahdi Khosravi
# What algorithms do you know for beltway reconstruction?

(Asked by: username_0 on 2013-07-09)

I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?   
**Beltway Reconstruction Problem**:   
Assume there is a set of non-identical integers between 0 and N, we only have pairwise distances of points of that set mod N, How can we reconstruct the original set using this?

**Tags:** ds.algorithms, nt.number-theory, comp-number-theory

> **Comments:**
> **username_1**: It's not quite the same problem, but some of the suggestions at http://cstheory.stackexchange.com/questions/17307/how-to-obtain-the-unknown-values-a-i-b-j-given-an-unordered-list-of-a-i-b-j-m?rq=1 look helpful.  
> **username_2**: [simultaneously cross-posted](http://mathoverflow.net/questions/136156/what-algorithms-do-you-know-for-beltway-reconstruction) on MO.  
> **username_2**: Our [site policy](http://meta.cstheory.stackexchange.com/a/231/) prohibits ***simultaneous*** **crossposting**: it duplicates effort and fractures discussion. Crossposting is permitted after a week has passed without a satisfying answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link to the copies in both directions.  
> **username_0**: I wasn't aware of this rule. Now what should I do?  

---

## 1 answers

### Answer by username_3 on 2013-07-09. Score: 2

Paul Lemke Steven S. Skiena Warren D. Smith, [Reconstructing Sets From Interpoint Distances](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.6172), gave backtracking algorithm that runs in time $O(n^n \log n)$ for the beltway reconstruction problem. As far as I know, this is the best known. The exact complexity of the problem is not known. It is not known to be in $P$ and neither known to be $NP$-complete.

> **Comments:**
> **username_0**: Thanks. I've read these two papers: Reconstruction of Integers from Pairwise Distances & Reconstructing Sets From Interpoint Distances. Do you know any other references?  
> **username_3**: No. I am not aware of any more recent references.  

---

