Probabilistic Location Problems with Discrete Demand Weights

摘要

In this article we consider four models for locating a facility on an undirected network with demand weights, which are independent discrete random variables. These problems include the probabilistic versions of two models for locating desirable facilities: the 1-median and 1-minimax problems and two problems for locating undesirable facilities: the 1-antimedian and 1-maximin problems. The article contains analysis of special cases where a solution is determined by solving deterministic versions of the problems and efficient algorithms to solve the problems in general.