Thumbnail - Request a copy

A new efficient heuristic for minimum set covering problem

Afif, Mohamed; Hifi, Mhand; Paschos, Vangelis; Zissimopoulos, Vassilis (1995), A new efficient heuristic for minimum set covering problem, The Journal of the Operational Research Society, 46, 10, p. 1260-1268. http://dx.doi.org/10.1057/jors.1995.173

Type
Article accepté pour publication ou publié
Date
1995
Journal name
The Journal of the Operational Research Society
Volume
46
Number
10
Publisher
Palgrave
Pages
1260-1268
Publication identifier
Metadata
Show full item record
Author(s)
Afif, Mohamed
Hifi, Mhand
Paschos, Vangelis
Zissimopoulos, Vassilis
Abstract (EN)
We solve approximately the minimum set covering problem by developing a new heuristic, which is essentially based on the flow algorithm originally developed by Ford and Fulkerson. We perform a comparative study of the performances (concerning solution qualities and execution times) of the flow algorithm as well as of the natural greedy heuristic for set covering originally studied by Johnson and Lovász.
Subjects / Keywords
Set covering; integer programming; heuristics; computational analysis; combinatorial analysis