Abstract
The turnpike problem is one of the few “natural” problems that are neither known to be NP-complete nor solvable by efficient algorithms. We seek to study this problem in a more general setting. We consider the generalized problem which tries to resolve set A = {a 1,a 2, ⋯ ,a n } from pairwise function values {f(a i ,a j ) | 1 ≤ i, j ≤ n} for a given bivariate function f. We call this problem the Number Reconstruction problem. Our results include efficient algorithms when f is monotone and non-trivial bounds on the number of solutions when f is the sum. We also generalize previous backtracking and algebraic algorithms for the turnpike problem such that they work for the family of anti-monotone functions and linear-decomposable functions. Finally, we propose an efficient algorithm for the string reconstruction problem, which is related to an approach to protein reconstruction.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abrams, Z., Chen, H.L.: The Simplified Partial Digest Problem: Hardness and a Probabilistic Analysis. In: RECOMB Satellite Meeting on DNA Sequencing Technologies and Computation (2004)
Blazewicz, J., Formanowicz, P., Kasprzak, M., Jaroszewski, M., Markiewicz, W.T.: Construction of DNA restriction maps based on a simplified experiment (2001)
Cieliebak, M., Eidenbenz, S.: Measurement errors make the partial digest problem NP-hard. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 379–390. Springer, Heidelberg (2004)
Cieliebak, M., Eidenbenz, S., Penna, P.: Noisy data make the partial digest problem NP-hard. In: Benson, G., Page, R.D.M. (eds.) WABI 2003. LNCS (LNBI), vol. 2812, pp. 111–123. Springer, Heidelberg (2003)
Dakic, T.: On the turnpike problem. PhD thesis, Simon Fraser University (2000)
Das, H., Orlitsky, A., Santhanam, N.: Order from disorder. In: Information Theory and Applications Workshop (2009)
Goldstein, L., Waterman, M.S.: Mapping DNA by stochastic relaxation. Advances in Applied Mathematics 8(2), 194–207 (1987)
Lemke, P., Skiena, S.S., Smith, W.D.: Reconstructing sets from interpoint distances. Discrete and computational geometry: The Goodman-Pollack Festschrift 25, 597–631
O’Bryant, K., Weisstein, E.: Lehmer’s Mahler measure problem. MathWorld–A Wolfram Web Resource
Pandurangan, G., Ramesh, H.: The restriction mapping problem revisited. Journal of Computer and System Sciences 65(3), 526–544 (2002)
Patterson, A.L.: A direct method for the determination of the components of interatomic distances in crystals. Zeitschr. Krist. 90, 517–542 (1935)
Patterson, A.L.: Ambiguities in the X-ray analysis of crystal structures. Phys. Review 65, 195–201 (1944)
Piccard, S.: Sur les Ensembles de Distances des Ensembles de Point d’un Espace Euclidean. Mem. Univ. Neuchatel 13 (1939)
Rosenblatt, J., Seymour, P.D.: The structure of homometric sets. SIAM Journal on Algebraic and Discrete Methods 3, 343 (1982)
Shamos, M.I.: Problems in computational geometry. Unpublished manuscript, Carnegie Mellon University, Pittsburgh, PA (1977)
Skiena, S.S., Sundaram, G.: A partial digest approach to restriction site mapping. Bulletin of Mathematical Biology 56(2), 275–294 (1994)
Smyth, C.J.: On the product of the conjugates outside the unit circle of an algebraic integer. Bulletin of the London Mathematical Society 3(2), 169 (1971)
Smyth, C.J.: The Mahler measure of algebraic numbers: a survey. Number Theory and Polynomials, 322 (2008)
Zhang, Z.: An exponential example for a partial digest mapping algorithm. Journal of Computational Biology 1(3), 235–239 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, S., Huang, Z., Kannan, S. (2009). Reconstructing Numbers from Pairwise Function Values. In: Dong, Y., Du, DZ., Ibarra, O. (eds) Algorithms and Computation. ISAAC 2009. Lecture Notes in Computer Science, vol 5878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10631-6_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-10631-6_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10630-9
Online ISBN: 978-3-642-10631-6
eBook Packages: Computer ScienceComputer Science (R0)