Optimization Online


Two-Dimensional Maximum p-Coverage Problem with Partial Coverage

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

Abstract: In this paper, we introduce a new generalization of the classical maximum p-coverage problem (MCP) in which p geometric objects of known dimensions are to be located such that their union covers maximum weight distributed on a two-dimensional plane using another set of geometric objects such as circles, rectangles, polygons, etc. We allow partial coverage in the foregoing generalization and denote this problem by MCP-PC. Using greedy approach, we develop an approximation algorithm to solve the MCP-PC and showcase that this algorithm has approximation ratio of 1- 1/e where e is the base of natural logarithm. We also discuss about the classes of applied problems which can be formulated as the MCP-PC.

Keywords: maximum p-coverage problem; greedy-based approximation algorithm; partial coverage; facility location; geographical informative systems; telerobotics

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: 09/04/2017

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