History

The problem of p-center has been widely approached from an algorithmic and accurate approach. The first studies were outlined by Hakimi, where the location of switching centers is optimized in a communications network and police stations on a road system and Kariv and Hakimi, who show that p-center in a general graph is NP-hard. Farahani and Hekmatfar provide a chapter on the state of the art of the problem in which it includes models, applications and heuristic and exact solution methods for jobs with greater relevance.

In a specific way we can say that the work of Elloumi et al, is one of the most significant works for the p-center in which a reformulation of the problem based on coverage radios as well as a solution methodology through a exact approach. Research on the p-center problem has been more limited. The problem was presented by Bar-Ilan, Kortsarz and Peleg for a problem of location of centers in distributed communications networks, developing a method of approximation in timepolynomial when the demand of each user is equal to 1, that is, unitary.

Khuller and Sussmann propose another approximation method, where each user has a demand unit and introduce a variant of the problem where multiple facilities can be located in a node. These approximation algorithms, an exact algorithm in time polynomial for trees in networks is developed by Jaeger and Goldberg, where the demand of the user is unitary and considering the case of the multiple p-center.

P-center problem

The p-center problem belongs to the maximum distance models. The objective of this model is to minimize the maximum distance between a demand node and its ease more close, given that you have a predetermined number of facilities to install. Known this model as a minimax problem and as an objective point problem, since it minimizes the distance from each demand location to the site of the facility as a goal separated, therefore, there is an objective for each demand location.

The problem of p-centers is a problem of localization that consists in placing p centers of service and assign clients to these centers in a way that minimizes the maximum distance between a client and his facility.

Location- Assignment (Location - Allocation)

The locations of potential supply and demand points, of ideal or real distances, and the costs of displacements of space friction, are presented as the main factors that produce different territorial configurations in the system.

The location-allocation models respond to the following characteristics:

x They are mathematical models since this language is considered as apt to grasp reality.

x They are meso-spatial models because the aspects to solve are found clearly delimited in a territory.

x They are normative models because you should look for the best solution to a given problem.

The location-allocation models are tools for decision making that they can be used prescriptively and descriptively.

Some elements that are taken in account are:

x Spatial Efficiency: estimated by adding distances between the offer and the demand.

x As a Spatial indicator, either the concept of coverage radius or, in other cases, the standard deviation of the distances that separate the affected population of the facilities.