Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0622.90060
Chaudhry, Sohail S.; Moon, I.Douglas; McCormick, S.Thomas
Conditional covering: Greedy heuristics and computational results. (English)
[J] Comput. Oper. Res. 14, 11-18 (1987). ISSN 0305-0548

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.

MSC 2000:: *90C10 Integer programming
90B05 Inventory management
65K05 Mathematical programming (numerical methods)
68Q25 Analysis of algorithms and problem complexity
05C70 Factorization, etc.
90C90 Appl. of mathematical programming

Keywords: facility location; conditional covering; set-covering; greedy heuristics; worst-case error bounds

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]