Optimization Online


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

Manish Bansal (bansal***at***vt.edu)

Abstract: 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.

Keywords: planar maximum coverage location problem; greedy approach; pseudo-greedy algorithm; partial coverage; spatial demand representation

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Category 3: Nonlinear Optimization (Other )

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


Entry Submitted: 09/04/2017
Entry Accepted: 09/04/2017
Entry Last Modified: 12/18/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society