×

zbMATH — the first resource for mathematics

The algebraic degree of geometric optimization problems. (English) Zbl 0647.90087
We apply Galois methods to certain fundamental geometric 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 the line-restricted Weber problem and its three-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 exists no exact algorithm under models of computation where the root of an algebraic equation is obtained using arithmetic operations and the extraction of kth 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.

MSC:
90C30 Nonlinear programming
90C99 Mathematical programming
68Q25 Analysis of algorithms and problem complexity
90B05 Inventory, storage, reservoirs
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] C. Bajaj, Geometric Optimization and Computational Complexity, Computer Science Technical Report TR84-629, Ph.D. thesis, Cornell University, Ithaca, NY, 1984.
[2] A. Baker,Transcendental Number Theory, Cambridge University Press, Cambridge, 1975. · Zbl 0297.10013
[3] Burns, J., Abstract definition of groups of degree eight, Amer. J. Math., 37, 195-214, (1915) · JFM 45.0251.01
[4] Butler, C.; McKay, J., The transitive groups of degree up to 11, Comm. Algebra, 11, 863-911, (1983) · Zbl 0518.20003
[5] Collins, G. E.; Loos, R.; Buchberger, B. (ed.); etal., Real zeros of polynomials, 84-94, (1982), Wien, New York
[6] R. Courant and H. Robbins,What is Mathematics?, Oxford University Press, Oxford, 1941.
[7] Engeler, E., Lower bounds by Galois theory, Astérisque, 38-39, 45-52, (1976) · Zbl 0355.02027
[8] L. Gaal,Classical Galois Theory with Examples, Markham, 1971.
[9] 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.
[10] R. L. Graham, Unsolved problem P73, problems and solutions,Bull. EATCS (1984), 205-206.
[11] I. N. Herstein,Topics in Algebra, 2nd ed., Wiley, New York, 1975. · Zbl 1230.00004
[12] D. E. Knuth,The Art of Computer Programming, vol. 2, 2nd edn., Addison-Wesley, Reading, MA, 1981. · Zbl 0477.65002
[13] Kuhn, H. W.; Abadie, J. (ed.), On a pair of dual non-linear programs, 37-54, (1967), Amsterdam
[14] Kung, H. T., The computational complexity of algebraic numbers, SIAM J. Numer. Anal., 12, 89-96, (1975)
[15] 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.
[16] 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. · Zbl 0454.65035
[17] McKay, J., Some remarks on computing Galois groups, SIAM J. Comput., 8, 344-347, (1979) · Zbl 0426.12015
[18] Z. A. Melzak,Companion to Concrete Mathematics, Wiley, New York, 1973. · Zbl 0254.26003
[19] Miller, G. A., Memoir on the substitution groups whose degree does not exceed eight, Amer. J. Math., 21, 287-337, (1899) · JFM 30.0133.04
[20] A. M. Odlyzko, Personal Communication, May 1985.
[21] Peskin, B. R.; Richman, D. R., A method to compute minimal polynomials, SIAM J. Algebraic Discrete Methods, 6, 292-299, (1985) · Zbl 0599.68039
[22] Rump, S. M., Polynomial minimum root separation, Math. Comp., 33, 327-336, (1979) · Zbl 0405.12018
[23] 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.
[24] Stauduhar, R. P., The determination of Galois groups, Math. Comp., 27, 981-996, (1973) · Zbl 0282.12004
[25] B. L. Van der Waerden,Modern Algebra, vol. 1, Ungar, New York, 1953.
[26] A. Weber,Theory of the Location of Industries (translated by Carl J. Friedrich), The University of Chicago Press, Chicago, 1937.
[27] H. Zassenhaus, On the group of an equation,Computers in Algebra and Number Theory, SIAM and AMS Proceedings, 69-88, 1971.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.