A NEW EFFICIENT HEURISTIC FOR THE MINIMUM SET COVERING PROBLEM

Authors
AFIF M HIFI M PASCHOS VT ZISSIMOPOULOS V
Citation
M. Afif et al., A NEW EFFICIENT HEURISTIC FOR THE MINIMUM SET COVERING PROBLEM, The Journal of the Operational Research Society, 46(10), 1995, pp. 1260-1268
Citations number
5
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
Journal title
The Journal of the Operational Research Society → ACNP
ISSN journal
01605682
Volume
46
Issue
10
Year of publication
1995
Pages
1260 - 1268
Database
ISI
SICI code
0160-5682(1995)46:10<1260:ANEHFT>2.0.ZU;2-0
Abstract
We solve approximately the minimum set covering problem by developing a new heuristic, which is essentially based on the flow algorithm orig inally developed by Ford and Fulkerson. We perform a comparative study of the performances (concerning solution qualities and execution time s) of the now algorithm as well as of the natural greedy heuristic for set covering originally studied by Johnson and Lovasz.