1

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?

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Mahdi Khosravi
  • 179
  • 6
  • 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. – David Eppstein Jul 09 '13 at 05:17
  • simultaneously cross-posted on MO. – Kaveh Jul 09 '13 at 08:37
  • 1
    Our site policy 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 Jul 09 '13 at 08:38
  • I wasn't aware of this rule. Now what should I do? – Mahdi Khosravi Jul 09 '13 at 08:56

1 Answers1

2

Paul Lemke Steven S. Skiena Warren D. Smith, Reconstructing Sets From Interpoint Distances, 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.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149