Planar Maximum Coverage Location Problem with Partial Coverage and General Spatial Representation of Demand and Service Zones

We introduce a new generalization of the classical planar maximum coverage location problem (PMCLP) in which demand zones and service zone of each facility are represented by spatial objects such as circles, polygons, etc., and are allowed to be located anywhere in a continuous plane. In addition, we allow partial coverage in its true sense, i.e., covering only part of a demand zone is allowed and the coverage accrued in the objective function as a result of this is proportional to the demand of the covered area only, and denote this generalization by PMCLP-PC-G. We present a greedy algorithm and a pseudo-greedy algorithm for it, and showcase that the solution value corresponding to the greedy (or pseudo-greedy) solution is within a factor of $1 - 1/e$ (or $1 - 1/e^{\eta}$) of the optimal solution value where $e$ is the base of natural logarithm and $\eta \leq 1$. These algorithmic and theoretical results generalize the similar results of Cornuejols et al. [Management Science, 23(8): 789-810, 1977] and Hochbaum and Pathria [NRL, 45(6): 615-627, 1998] for special cases of PMCLP-PC-G, where demand zones are represented by points and partial coverage is not allowed, respectively, and the locations of facilities belong to a finite set of pre-specified candidate positions.

Citation

Refer to https://arxiv.org/abs/2012.09063 for latest updated version.