ScholarLens Back to search
1982•SIAM Journal on Algebraic and Discrete MethodsRequires access

On the Greedy Heuristic for Continuous Covering and Packing Problems

Marshall L. Fisher, Laurence A. Wolsey

Open publisher page 48 citations

Abstract

Worst-case bounds are given on the performance of the greedy heuristic for a continuous version of the set covering problem. This generalizes results of Chvatal, Johnson and Lovasz for the 0-1 covering problem. The results for the greedy heuristic and for other heuristics are obtained by treating the covering problem as a limiting case of a generalized location problem for which worst-case results are known. An alternative approach involving dual greedy heuristics leads also to worst-case bounds for continuous packing problems.

About this research paper

What this paper is about

Worst-case bounds are given on the performance of the greedy heuristic for a continuous version of the set covering problem. This generalizes results of Chvatal, Johnson and Lovasz for the 0-1 covering problem. The results for the greedy heuristic and for other heuristics are obtained by treating the covering problem as a limiting case of a generalized location problem for which worst-case results are known. An alternative approach involving dual greedy heuristics leads also to worst-case bounds for continuous packing problems.

Why it matters

OpenAlex reports 48 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Worst-case bounds are given on the performance of the greedy heuristic for a continuous version of the set covering problem. This generalizes results of Chvatal, Johnson and Lovasz for the 0-1 covering problem. The results for the greedy heuristic and for other heuristics are obtained by treating the covering problem as a limiting case of a generalized location problem for which worst-case results are known. An alternative approach involving dual greedy heuristics leads also to worst-case bounds for continuous packing problems.

Key concepts: Heuristics, Greedy algorithm, Mathematics, Mathematical optimization, Heuristic, Limiting, Set (abstract data type), Greedy randomized adaptive search procedure

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
On the Greedy Heuristic for Continuous Covering and Packing Problems — Research Paper | ScholarLens