Bicriteria and restricted 2-Facility Weber Problems

In this paper we look at two interesting extensions to the classical 2-Facility Weber Problem in ℝ d : At first problems are investigated where we do not allow the optimal locations to be in a specific region. Efficient algorithms for this Global Optimization problem are presented as well as new structural results. Secondly we consider 2-Facility Weber Problems with two decision makers where each decision maker can choose his own preferences for the location problem. We give an efficient algorithm for determining all pareto locations for this multicriteria problem as well as a polynomial description of the set of all pareto locations (in ℝ 2d ). All the results presented in this paper are based on a discretization of the original continuous problem using geometrical and combinatorial arguments. The time complexity of all the presented algorithms isO(dM logM), whereM is the number of existing facilities. Copyright Physica-Verlag 1997