The facility location problem is a classical one with various forms, the most well-known being the k-median problem when the number of facilities is known (k) and the UFL (uncapacitated facility location) problem when both the number and the location of the facilities need to be optimized given that there is a cost for their maintenance. The solution of such problems answers many modern networking problems like placing a server, a virtual machine, or a virtual network function in a network environment that can also be a cloud or a fog computing environment.
In the general case, these problems are NP-hard and require global knowledge of the network parameters to be solved. Even though there are approximation approaches that reduce the complexity, the global knowledge requirement still remains. However, this is not a realistic approach in modern network environments that are inherently dynamic (frequent topology changes, diverse user demands, etc.). Therefore, the traditional centralized approaches are not suitable since they require the continuous accumulation of network data that change and may become obsolete before being processed. Eventually, these are not scalable approaches.
Example of a 2-median problem for a general network topology. Starting from arbitrary initial positions, how two service facility may move (if possible) to their optimal locations?