The study of facility location problems (FLP), also known as location analysis, is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering factors like avoiding placing hazardous materials near housing, and competitors' facilities.
A simple facility location problem is the Weber problem, in which a single facility is to be placed, with the only optimization criterion being the minimization of the weighted sum of distances from a given set of point sites.
A number of approximation algorithms have been developed for the facility location problem and many of its variants.
Without assumptions on the set of distances between clients and sites (in particular, without assuming that the distances satisfy the triangle inequality), the problem is known as non-metric facility location and can be approximated to within a factor O(log n).
[1] This factor is tight, via an approximation-preserving reduction from the set cover problem.
If we assume distances between clients and sites are undirected and satisfy the triangle inequality, we are talking about a metric facility location (MFL) problem.
It has been proven that exact solution of k-center problem is NP hard.
[4] [5] [6] Approximation to the problem was found to be also NP hard when the error is small.
One approach based on the coreset concept is proposed with execution complexity of
[11] The author claims that the running time is much less than the worst case and thus it's possible to solve some problems when k is small (say k < 5).
Farthest-point clustering For the hardness of the problem, it's impractical to get an exact solution or precise approximation.
The approximation is referred to as the farthest-point clustering (FPC) algorithm, or farthest-first traversal.
As per the performance of execution, the time complexity is later improved to O(n log k) with box decomposition technique.
In the case of the Euclidean metric, it is known as the largest empty sphere problem.
The planar single-facility case (largest empty circle problem) may be solved in optimal time Θ(n log n).
[12][13] Facility location problems are often solved as integer programs.
In this context, facility location problems are often posed as follows: suppose there are
customers, in order to satisfy some fixed demand at minimum cost.
denote the maximum amount of product that can be produced by facility
The remainder of this section follows[14] In our initial formulation, introduce a binary variable
Another formulation possibility for the uncapacitated facility location problem is to disaggregate the capacity constraints (the big-
[15] In healthcare, incorrect facility location decisions have a serious impact on the community beyond simple cost and service metrics; for instance, hard-to-access healthcare facilities are likely to be associated with increased morbidity and mortality.
[18] To see how one might view (read "transform" or "reduce") a centroid-based clustering problem as a (metric) facility location problem, view each data point in the former as a demand point in the latter.
Suppose that the data to be clustered are elements of a metric space
to be the pairwise distances between location-demand point pairs (e.g., see metric k-center).
Let us see how a solution to our constructed facility location problem also achieves such a partition.
This achieves the partitioning provided that the facility location problem's costs
are defined such that they are the images of the centroid-based clustering problem's distance function.
Furthermore, see that in our above definition of the facility location problem that the objective function
For example, one might choose to minimize the sum of distances from each location to each of its assigned demand points (à la the Weber problem), or one might elect to minimize the maximum of all such distances (à la the 1-center problem).