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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ cross-posted on Theoretical Computer Science. $\endgroup$– KavehJul 9, 2013 at 8:38
-
$\begingroup$ See also the MO question Difference Sets, which also discusses the beltway reconstruction problem. $\endgroup$– Joseph O'RourkeJul 9, 2013 at 10:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
A relatively recent result for a sparse case can be found here (see Algorithm 2). It’s a probabilistic polynomial-time algorithm.
-
$\begingroup$ Thanks. I've read these two papers: Reconstruction of Integers from Pairwise Distances & Reconstructing Sets From Interpoint Distances. Any other references? $\endgroup$ Jul 9, 2013 at 7:16