# zbMATH — the first resource for mathematics

Classical and inverse median location problems under uncertain environment. (English) Zbl 1436.90074
Summary: In this paper, we first consider the classical $$p$$-median location problem on a network in which the vertex weights and the distances between vertices are uncertain variables. The uncertainty distribution of the optimal objective value of the $$p$$-median problem is given and the concepts of the $$\alpha$$-$$p$$-median, the most $$p$$-median and the expected $$p$$-median are introduced. Then, it is shown that the uncertain $$p$$-median problem is NP-hard on general networks. However, if the underlying network is a tree, an efficient algorithm for the uncertain 1-median problem with linear time complexity is proposed. Finally, we investigate the inverse 1-median problem on a tree with uncertain vertex weights and present a programming model for the problem. Then, it is shown that the proposed model can be reformulated into a deterministic programming model.
##### MSC:
 90B80 Discrete location and assignment 90C27 Combinatorial optimization