1
$\begingroup$

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?

$\endgroup$

closed as off-topic by Kaveh Jul 9 '13 at 8:38

  • This question does not appear to be a research-level question in theoretical computer science. For more information, please see scope.
If this question can be reworded to fit the rules in the help center, please edit the question.

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

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.

$\endgroup$
  • $\begingroup$ Thanks. I've read these two papers: Reconstruction of Integers from Pairwise Distances & Reconstructing Sets From Interpoint Distances. Do you know any other references? $\endgroup$ – Mahdi Khosravi Jul 9 '13 at 7:19
  • 1
    $\begingroup$ No. I am not aware of any more recent references. $\endgroup$ – Mohammad Al-Turkistany Jul 9 '13 at 7:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.