Algebraic optimization: The Fermat-Weber location problem
Tóm tắt
The Fermat-Weber location problem is to find a point in ℝ
n
that minimizes the sum of the (weighted) Euclidean distances fromm given points in ℝ
n
. In this work we discuss some relevant complexity and algorithmic issues. First, using Tarski's theory on solvability over real closed fields we argue that there is an infinite scheme to solve the problem, where the rate of convergence is equal to the rate of the best method to locate a real algebraic root of a one-dimensional polynomial. Secondly, we exhibit an explicit solution to the strong separation problem associated with the Fermat-Weber model. This separation result shows that anε-approximation solution can be constructed in polynomial time using the standard Ellipsoid Method.
Tài liệu tham khảo
C. Bajaj, “Geometric optimization and computational geometry,” Ph.D. Thesis, Computer Science Technical Report TR84-629, Cornell University (Ithaca, NY, 1984).
M. Ben-Or, D. Kozen and J. Rief, “The complexity of elementary algebra and geometry,”Journal of Computer and System Sciences 32 (1986) 251–264.
M. Blum, R.W. Floyd, V.R. Pratt, R.L. Rivest and R.E. Tarjan, “Time bounds for selection,”Journal of Computer and System Sciences 7 (1972) 448–461.
G.E. Collins, “Quantifier elimination for real closed fields by cylindric algebraic decomposition,”Proceedings 2nd GI Conference on Automata Theory and Formal Languages, Lecture Notes in Computer Science, Vol. 35 (Springer-Verlag, Berlin, 1975) pp. 134–183.
M.R. Garey, R.L. Graham and D.S. Johnson, “Some NP-complete geometric problems,”Proceedings 8th Annual ACM Symposium on the Theory of Computing (1976) 10–22.
R.L. Graham, “Unsolved problem P73,”Problems and Solutions, Bulletin of the EATCS (1984) 205–206.
M. Grötschel, L. Lovasz and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,”Combinatorica 1 (1981) 169–197.
G.H. Hardy, J.E. Littlewood, G. Polya,Inequalities (Cambridge University Press, London, 1943).
R. Kannan, A.K. Lenstra and L. Lovasz, “Polynomial factorisation and nonrandomness of bits of algebraic and some transcendental numbers,”Proceedings 16th Annual ACM Symposium on Theory of Computing (1984) 191–200.
D. Kozen and C.K. Yap, “Algebraic cell decomposition in NC,”Proceedings 26th Annual Symposium on Foundations of Computer Science (1985) 515–521.
H.W. Kuhn, “On a pair of dual nonlinear programs,” in: J. Abadie, ed.,Nonlinear Programming (North-Holland, Amsterdam, 1967) pp. 38–54.
L. Lovasz,An Algorithmic Theory of Numbers, Graphs and Convexity, Monograph (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1986).
Z.A. Melzak,Companion to Concrete Mathematics (John Wiley & Sons, New York, 1973).
J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York and London, 1970).
M.L. Overton, “A quadratically convergent method for minimizing a sum of euclidean norms,”Mathematical Programming 27 (1983) 34–63.
A. Tarski,A Decision Method for Elementary Algebra and Geometry, Second Edition, revised (University of California Press, Berkeley and Los Angeles, CA, 1951).
A. Weber,Theory of the Location of Industries, translated by Carl J. Friedrich (The University of Chicago Press, Chicago, IL, 1937).