Location Problems with Continuous Demand and Unreliable Facilities: Applications of Families of Incremental Voronoi Diagrams

We consider conditional facility location problems with unreliable facilities that
can fail with known probabilities. The demand is uniformly distributed over a convex polygon in the rectilinear plane where a number of facilities are already present, and it is required to optimally locate another facility. We analyze properties of the expo- nential family of incremental Voronoi diagrams associated with possible realizations of the set of operational facilities, and, based on this analysis, present polynomial algorithms for three conditional location problems. The approach can be extended to various other conditional location problems with continuous demand and unreliable facilities, under different probabilistic models including ones with correlated facility
failures.