Abstract
In this paper we apply Galois methods to certain fundamentalgeometric optimization problems whose exact computational complexity has been an open problem for a long time. In particular we show that the classic Weber problem, along with theline-restricted Weber problem and itsthree-dimensional version are in general not solvable by radicals over the field of rationals. One direct consequence of these results is that for these geometric optimization problems there existsno exact algorithm under models of computation where the root of an algebraic equation is obtained using arithmetic operations and the extraction ofkth roots. This leaves only numerical or symbolic approximations to the solutions, where the complexity of the approximations is shown to be primarily a function of the algebraic degree of the optimum solution point.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
C. Bajaj, Geometric Optimization and Computational Complexity, Computer Science Technical Report TR84-629, Ph.D. thesis, Cornell University, Ithaca, NY, 1984.
A. Baker,Transcendental Number Theory, Cambridge University Press, Cambridge, 1975.
J. Burns, Abstract definition of groups of degree eight,Amer. J. Math. 37 (1915), 195–214.
C. Butler and J. McKay, The transitive groups of degree up to 11,Comm. Algebra 11 (1983), 863–911.
G. E. Collins and R. Loos, Real zeros of polynomials, inComputing Supplementum, vol. 4 (B. Buchbergeret al., eds.), 84–94, Springer-Verlag, Wien, New York, 1982.
R. Courant and H. Robbins,What is Mathematics?, Oxford University Press, Oxford, 1941.
E. Engeler, Lower bounds by Galois theory,Astérisque 38–39 (1976), 45–52.
L. Gaal,Classical Galois Theory with Examples, Markham, 1971.
M. R. Garey, R. L. Graham, and D. S. Johnson, Some NP-complete geometric problems,Proceedings of the Eighth Symposium on the Theory of Computing, 10–22, 1976.
R. L. Graham, Unsolved problem P73, problems and solutions,Bull. EATCS (1984), 205–206.
I. N. Herstein,Topics in Algebra, 2nd ed., Wiley, New York, 1975.
D. E. Knuth,The Art of Computer Programming, vol. 2, 2nd edn., Addison-Wesley, Reading, MA, 1981.
H. W. Kuhn, On a pair of dual non-linear programs, inNon-Linear Programming (J. Abadie, ed.), 37–54, North-Holland, Amsterdam, 1967.
H. T. Kung, The computational complexity of algebraic numbers,SIAM J. Numer. Anal. 12 (1975), 89–96.
S. Landau and G. L. Miller, Solvability by radicals in polynomial time,Proceedings of the 15th Annual Symposium on the Theory of Computing, 140–151, 1983.
J. D. Lipson, Newton's method: a great algebraic algorithm,Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation (SYMSAC), 260–270, 1976.
J. McKay, Some remarks on computing Galois groups,SIAM J. Comput. 8 (1979), 344–347.
Z. A. Melzak,Companion to Concrete Mathematics, Wiley, New York, 1973.
G. A. Miller, Memoir on the substitution groups whose degree does not exceed eight,Amer. J. Math. 21 (1899), 287–337.
A. M. Odlyzko, Personal Communication, May 1985.
B. R. Peskin and D. R. Richman, A method to compute minimal polynomials,SIAM J. Algebraic Discrete Methods 6 (1985), 292–299.
S. M. Rump, Polynomial minimum root separation,Math. Comp. 33 (1979), 327–336.
J. T. Schwartz, Polynomial Minimum Root Separation (Note to a Paper of S. M. Rump), Robotics Research Technical Report No. 39, New York University, 1985.
R. P. Stauduhar, The determination of Galois groups,Math. Comp. 27 (1973), 981–996.
B. L. Van der Waerden,Modern Algebra, vol. 1, Ungar, New York, 1953.
A. Weber,Theory of the Location of Industries (translated by Carl J. Friedrich), The University of Chicago Press, Chicago, 1937.
H. Zassenhaus, On the group of an equation,Computers in Algebra and Number Theory, SIAM and AMS Proceedings, 69–88, 1971.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bajaj, C. The algebraic degree of geometric optimization problems. Discrete Comput Geom 3, 177–191 (1988). https://doi.org/10.1007/BF02187906
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187906