Algebraic optimization: The Fermat-Weber location problem (Q584057): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
This paper discusses some complexity and algorithmic issues concerning the well-known Fermat-Weber problem, which asks for the determination of a point minimizing the weighted sum of Euclidean distances to a given finite set of points in n-space, assumed here to have rational coordinates. First it is argued that such a solution is algebraic, and that the characteristic polynomials of the optimal value and solution coordinates may be obtained by a finite number of elementary arithmetic operations (although exactly how this is to be done efficiently is unknown), together with associated intervals in which the sought values are the unique roots. Any rootfinding method would then solve the problem, thus yielding a solution method with rate of convergence equal to that of the best one-dimensional rootfinding method for polynomials. Next it is shown how to solve the strong separation problem associated with the Fermat-Weber model. This leads, by way of an ellipsoid method to a polynomial method to construct an approximate solution of fixed accuracy. | |||
Property / review text: This paper discusses some complexity and algorithmic issues concerning the well-known Fermat-Weber problem, which asks for the determination of a point minimizing the weighted sum of Euclidean distances to a given finite set of points in n-space, assumed here to have rational coordinates. First it is argued that such a solution is algebraic, and that the characteristic polynomials of the optimal value and solution coordinates may be obtained by a finite number of elementary arithmetic operations (although exactly how this is to be done efficiently is unknown), together with associated intervals in which the sought values are the unique roots. Any rootfinding method would then solve the problem, thus yielding a solution method with rate of convergence equal to that of the best one-dimensional rootfinding method for polynomials. Next it is shown how to solve the strong separation problem associated with the Fermat-Weber model. This leads, by way of an ellipsoid method to a polynomial method to construct an approximate solution of fixed accuracy. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Frank Plastria / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90B05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C27 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q25 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 4133803 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
location theory | |||
Property / zbMATH Keywords: location theory / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
algebraic optimization | |||
Property / zbMATH Keywords: algebraic optimization / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Fermat-Weber problem | |||
Property / zbMATH Keywords: Fermat-Weber problem / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
weighted sum of Euclidean distances | |||
Property / zbMATH Keywords: weighted sum of Euclidean distances / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
characteristic polynomials | |||
Property / zbMATH Keywords: characteristic polynomials / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
ellipsoid method | |||
Property / zbMATH Keywords: ellipsoid method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
polynomial method | |||
Property / zbMATH Keywords: polynomial method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
approximate solution | |||
Property / zbMATH Keywords: approximate solution / rank | |||
Normal rank |
Revision as of 19:29, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algebraic optimization: The Fermat-Weber location problem |
scientific article |
Statements
Algebraic optimization: The Fermat-Weber location problem (English)
0 references
1990
0 references
This paper discusses some complexity and algorithmic issues concerning the well-known Fermat-Weber problem, which asks for the determination of a point minimizing the weighted sum of Euclidean distances to a given finite set of points in n-space, assumed here to have rational coordinates. First it is argued that such a solution is algebraic, and that the characteristic polynomials of the optimal value and solution coordinates may be obtained by a finite number of elementary arithmetic operations (although exactly how this is to be done efficiently is unknown), together with associated intervals in which the sought values are the unique roots. Any rootfinding method would then solve the problem, thus yielding a solution method with rate of convergence equal to that of the best one-dimensional rootfinding method for polynomials. Next it is shown how to solve the strong separation problem associated with the Fermat-Weber model. This leads, by way of an ellipsoid method to a polynomial method to construct an approximate solution of fixed accuracy.
0 references
location theory
0 references
algebraic optimization
0 references
Fermat-Weber problem
0 references
weighted sum of Euclidean distances
0 references
characteristic polynomials
0 references
ellipsoid method
0 references
polynomial method
0 references
approximate solution
0 references