Finite Dominating Sets for Network Location Problems

From MaRDI portal





The paper deals with location problems with the goal to place a given number of servers at nodes or arcs of some network to minimize a cost function. The cost function depends on the distances between node and server locations or between different server locations. The authors aim at answering the question whether there is any finite set of locations in the network to which some optimal solution of the location problem must belong. Such a set of points is called finite dominating set (FDS) and its specification enables to construct an effective algorithm for the solution of the location problem. The paper contains a large survey of previous results and provides a comprehensive theory on this topic. The theory is based on 1-dominance which is a property of a large set of cost functions. This property is used in the theory to prove that FDS for easy solvable 1-server problem is FDS for \(p\)-server problem as well. Most of the previous results and their further generalization presented in the paper follows the 1-dominance and the appropriate theorems. Using the theory it is possible to get FDS easily for the generalized \(p\)- median problem, the generalized \(p\)-center problem, the generalized cent- dian problem and for the generalized obnoxious 1-center problem.




Cited in
(49)








This page was built for publication: Finite Dominating Sets for Network Location Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3981511)