# What algorithms do you know for beltway reconstruction? [closed]

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?

• It's not quite the same problem, but some of the suggestions at cstheory.stackexchange.com/questions/17307/… look helpful. – David Eppstein Jul 9 '13 at 5:17
• – Kaveh Jul 9 '13 at 8:37
• 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 9 '13 at 8:38
• I wasn't aware of this rule. Now what should I do? – Mahdi Khosravi Jul 9 '13 at 8:56

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.