Solving nonconvex planar location problems by nite dominating sets

Abstract

It is well-known that some of the classical location problems with polyhedral gauges can be solved in polynomial time by nding a fi nite dominating set, i.e. a finite set of candidates guaranteed to contain at least one optimal location. In this paper it is fi rst established that this result holds for a much larger class of problems than currently considered in the literature. The model for which this result can be proven includes, for instance, location problems with attraction and repulsion, and location-allocation problems. Next, it is shown that the approximation of general gauges by polyhedral ones in the objective function of our general model can be analyzed with regard to the subsequent error in the optimal ob jective value. For the approximation problem two di erent approaches are described, the sandwich procedure and the greedy algorithm. Both of these approaches lead - for fixed e - to polynomial approximation algorithms with accuracy for solving the general model considered in this paper.