On the Continuous Fermat-Weber Problem: A Geometric Approach to Facility Location
Title: On the Continuous Fermat-Weber Problem: A Geometric Approach to Facility Location
Abstract: This research focuses on the continuous Fermat-Weber problem, a facility location problem that aims to find one or more center points to minimize the average distance to a set of points in a demand region. The average is computed as an integral over the relevant region, rather than a discrete sum of distances. The resulting problems are inherently geometric, requiring analysis techniques of computational geometry.
The study provides polynomial-time algorithms for various versions of the L11-median (Fermat-Weber) problem. It also considers the multiple-center version of the L1k-median problem, proving it to be NP-hard for large k.
Keywords: location theory, Fermat-Weber problem, k-median, median, continuous demand, computational geometry, geometric optimization, shortest paths, rectilinear norm, computational complexity
Main Research Question: How can we efficiently solve the continuous Fermat-Weber problem for various versions of the L11-median and L1k-median problems?
Methodology: The study uses techniques from computational geometry to solve the continuous Fermat-Weber problem. It proposes polynomial-time algorithms for various versions of the L11-median (Fermat-Weber) problem and the multiple-center version of the L1k-median problem.
Results: The research shows that the continuous Fermat-Weber problem can be efficiently solved for various versions of the L11-median and L1k-median problems using polynomial-time algorithms. It also proves that the multiple-center version of the L1k-median problem is NP-hard for large k.
Implications: The findings of this study have significant implications for the field of facility location problems. The proposed algorithms can be applied to real-world problems where the demand points are continuous and the objective is to minimize the average distance to these points. The proof of NP-hardness for the multiple-center version of the L1k-median problem provides a theoretical boundary on the complexity of these problems.
Significance: This research contributes to the existing body of knowledge on facility location problems by providing efficient algorithms for solving the continuous Fermat-Weber problem for various versions of the L11-median and L1k-median problems. The results have practical implications for real-world applications and provide theoretical insights into the complexity of these problems.
Link to Article: https://arxiv.org/abs/0310027v1 Authors: arXiv ID: 0310027v1