Optimization Online


On Solving General Planar Maximum Coverage Location Problem with Partial Coverage

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

Abstract: In this paper, 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 two-dimensional spatial objects such as circles, polygons, etc. In addition, we allow partial coverage in the foregoing generalization, 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 part only. We denote this problem by PMCLP-PC, and present a greedy algorithm and a pseudo-greedy algorithm for it. We 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 <= 1. We also discuss about applications of the PMCLP-PC beyond location analytics.

Keywords: maximum coverage location problem; greedy approach; pseudo-greedy algorithm; partial coverage; facility location

Category 1: Combinatorial Optimization (Approximation Algorithms )

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

Category 3: Nonlinear Optimization (Other )

Citation: B12, ISE, Virginia Tech, Sept 2017

Download: [PDF]

Entry Submitted: 09/04/2017
Entry Accepted: 09/04/2017
Entry Last Modified: 01/10/2018

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