Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The computational complexity of simultaneous diophantine approximation problems
Lagarias J. SIAM Journal on Computing14 (1):196-209,1985.Type:Article
Date Reviewed: Jan 1 1986

This paper considers the computational complexity of algorithms to find good simultaneous approximations to a given vector of d rational numbers. Such problems have a number of important applications. The goodness of an approximation is measured by the sup norm.

After surveying the work of Lenstra, Lenstra, and Lovasz [1] on polynomial time algorithms, the author proves that certain natural simultaneous diophantine approximation problems are NP-hard. Two consequences are derived which suggest that the problem of locating best simultaneous approximations is computationally harder than that of locating good simultaneous approximations. The majority of the paper consists of proofs of these results. Two conjectures for further work are also presented.

Reviewer:  G. J. Davis Review #: CR109677
1) Lenstra, A. K.; Lenstra, H. W., Jr.; and Lovasz, L.Factoring polynomials with rational coefficients, Math. Annal. 261 (1982), 515–534.
Bookmark and Share
 
Numerical Algorithms And Problems (F.2.1 )
 
 
Rational Approximation (G.1.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Numerical Algorithms And Problems": Date
On the computational complexity of ordinary differential equations
Ko K. (ed) Information and Control 58(1-3): 157-194, 1984. Type: Article
Jun 1 1985
Parallel and distributed computation: numerical methods
Bertsekas D., Tsitsiklis J., Prentice-Hall, Inc., Upper Saddle River, NJ, 1989. Type: Book (9789780136487005)
Apr 1 1990
A fast, reliable algorithm for calculating Padé-Hermite forms
Cabay S., Labahn G.  Symbolic and algebraic computation (, Portland, OR, Jul 17-19, 1989)1001989. Type: Proceedings
Nov 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy