Solving nonconvex planar location problems by finite dominating sets

It is well-known that some of the classical location problems with polyhedr al gauges can be solved in polynomial time by finding a finite dominating s et, i.e. a finite set of candidates guaranteed to contain at least one opti mal location. In this paper it is first established that this result holds for a much lar ger class of problems than currently considered in the literature. The mode l for which this result can be proven includes, for instance, location prob lems with attraction and repulsion, and location-allocation problems. Next, it is shown that the approximation of general gauges by polyhedral on es in the objective function of our general model can be analyzed with rega rd to the subsequent error in the optimal objective value. For the approxim ation problem two different approaches are described, the sandwich procedur e and the greedy algorithm. Both of these approaches lead - for fixed epsil on - to polynomial approximation algorithms with accuracy epsilon for solvi ng the general model considered in this paper.