An exact algorithm for the maximal covering problem

Brian T. Downs and Jeffrey D. Camm

Naval Research Logistics (NRL), 1996, vol. 43, issue 3, 435-461

Abstract: This article develops a robust, exact algorithm for the maximal covering problem (MCP) using dual‐based solution methods and greedy heuristics in branch and bound. Based on tests using randomly generated problems with problem parameters similar to those in the existing literature, the hybrid approach developed in this work appears to be effective over a wide range of MCP model parameters. The method is further validated on problems constructed from three real‐world data sets. The extensive computational study compares the new method with other existing exact methods using problems that are as big, or larger than, those used in previous work on MCP. The results show that the proposed method is effective in most instances of MCP. In particular, it is shown that bounding schemes using Lagrangian relaxation are effective on MCP as a method of obtaining both exact and heuristic solutions. © 1996 John Wiley & Sons, Inc.

Date: 1996
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199604)43:33.0.CO;2-A

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:43:y:1996:i:3:p:435-461

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().