Conditional covering: greedy heuristics and computational results
type: Item
instance of: scholarly article
title: Conditional covering: greedy heuristics and computational results
zbMATH Open document ID: 0622.90060
DOI: 10.1016/0305-0548(87)90053-0
author: Sohail S. Chaudhry
author: I. Douglas Moon
author: S. Thomas McCormick
published in: Computers \& Operations Research
publication date: 1987-01-01T00:00:00Z
review text: The conditional covering problem is a variation of the set-covering problem which seeks a minimum set of facility sites that will cover not only the given demand points but also one another. Finding an exact solution to the problem is difficult and costly. This paper presents seven greedy heuristics with computational results. Compared with exact integer solutions obtained from LINDO, most of these heuristics seem to perform quite satisfactorily for relatively large problems. The paper also discusses worst-case error bounds for the two best performing heuristics based on the best known bound for set-covering.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90B05
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C90
zbMATH DE Number: 4010213
zbMATH Keywords: facility location
zbMATH Keywords: conditional covering
zbMATH Keywords: set-covering
zbMATH Keywords: greedy heuristics
zbMATH Keywords: worst-case error bounds
MaRDI profile type: Publication
full work available at URL: 0305-0548(87)90053-0
OpenAlex ID: W2052778038
cites work: An Analysis of Network Location Problems with Distance Constraints
cites work: Approximating the Performance of Urban Emergency Service Systems
cites work: Q4198056
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: Approximation algorithms for combinatorial problems
cites work: On the ratio of optimal integral and fractional covers
cites work: The Location of Emergency Service Facilities
cites work: Worst-Case Analysis of Heuristic Algorithms
cites work: Worst case analysis of a class of set covering heuristics
description: scientific article; zbMATH DE number 4010213