  We consider a generalization of the classical planar maximum coverage
location problem (PMCLP) in which partial coverage is allowed, facilities have
adjustable quality of service (QoS) or service range, and demand zones and
service zone of each facility are represented by two-dimensional spatial
objects such as rectangles, circles, polygons, etc. We denote this
generalization by PMCLP-PC-QoS. A key challenge in this problem is to
simultaneously decide position of the facilities on a continuous
two-dimensional plane and their QoS. We present a greedy algorithm and a
pseudo-greedy algorithm for it, and provide their approximation ratios. We also
investigate theoretical properties and propose exact algorithms for solving:
(1) PMCLP-PC-QoS where demand and service zones are represented by
axis-parallel rectangles (denoted by PMCLP-PCR-QoS), which also has
applications in camera surveillance and satellite imaging; and (2) one
dimensional PMCLP-PC-QoS which has applications in river cleanups. These
results extend and strengthen the only known exact algorithm for PMCLP-PCR-QoS
with fixed and same QoS by Bansal and Kianfar [INFORMS Journal on Computing
29(1), 152-169, 2017]. We present results of our computational experiments
conducted to evaluate the performance of our proposed exact and approximation
algorithms.
