Algebraic optimization: The Fermat-Weber location problem
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.
- A quadratically convergent method for minimizing a sum of euclidean norms
- scientific article; zbMATH DE number 3588048 (Why is no real title available?)
- scientific article; zbMATH DE number 3291744 (Why is no real title available?)
- scientific article; zbMATH DE number 3381785 (Why is no real title available?)
- scientific article; zbMATH DE number 3401212 (Why is no real title available?)
- scientific article; zbMATH DE number 3068536 (Why is no real title available?)
- Interactions Between Self and Parametrically Excited Motions in Articulated Tubes
- The complexity of elementary algebra and geometry
- The ellipsoid method and its consequences in combinatorial optimization
- Time bounds for selection
- The projection median of a set of points
- Single facility collection depots location problem in the plane
- Location problems with costs being sums of powers of Euclidean distances
- Heuristics and bounds for the travelling salesman location problem on the plane
- Geometric median and robust estimation in Banach spaces
- Stock cutting to minimize cutting length
- Accelerating convergence in the Fermat-Weber location problem
- The Fermat-Torricelli point and isosceles tetrahedra
- Improved upper bounds for the Steiner ratio
- Facility location problems with uncertainty on the plane
- Fast approximations for sums of distances, clustering and the Fermat-Weber problem
- Fuzzy disk for covering fuzzy points
- The Fermat-Weber location problem revisited
- Data loci in algebraic optimization
- A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
- The optimal solution set of the multi-source Weber problem
- Matching point sets with respect to the earth mover's distance
- New models for locating a moving service facility
- On the Fermat-Weber center of a convex object
- On the Fermat-Weber point of a polygonal chain and its generalizations
- The Fermat-Torricelli problem. I: A discrete gradient-method approach
- Approximating generalized distance functions on weighted triangulated surfaces with applications
- Robust and scalable Bayes via a median of subset posterior measures
- A polynomial time algorithm for solving the fermat-weber location problem with mixed norms
- One-dimensional \(k\)-center on uncertain data
- Approximating the distribution of the median and other robust estimators on uncertain data
- New algorithms for facility location problems on the real line
- A modified Weiszfeld algorithm for the Fermat-Weber location problem
- A new heuristic for the Euclidean Steiner tree problem in \(\mathbb{R}^n\)
- Efficient subspace approximation algorithms
- Further analysis of the Weber problem
- Reviewing extensions and solution methods of the planar Weber single facility location problem
- Mathematical optimization modelling for group counterfactual explanations
- On the probability that the optimal solution of the Weber location problem is at a demand point
- Computing generalized higher-order Voronoi diagrams on triangulated surfaces
- On stars and Steiner stars
This page was built for publication: Algebraic optimization: The Fermat-Weber location problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q584057)
