Thumbnail - Request a copy

A neural network for the minimum set covering problem

Zissimopoulos, Vassilis; Paschos, Vangelis; Hifi, Mhand (2000), A neural network for the minimum set covering problem, Chaos, Solitons and Fractals, 11, 13, p. 2079-2089. http://dx.doi.org/10.1016/S0960-0779(99)00104-6

Type
Article accepté pour publication ou publié
Date
2000
Journal name
Chaos, Solitons and Fractals
Volume
11
Number
13
Publisher
Elsevier
Pages
2079-2089
Publication identifier
Metadata
Show full item record
Author(s)
Zissimopoulos, Vassilis
Paschos, Vangelis
Hifi, Mhand
Abstract (EN)
We solve approximately the weighted set covering problem by putting together a neural network model, the Boltzmann machine (BM), and some combinatorial ideas. We compare the solutions provided by the network with the ones obtained using the greedy set covering heuristic and the Lagrangian heuristic developed by Beasley. Moreover, we use a simple and intuitive polynomial decomposition schema treating large instances by decomposing them into smaller ones. Finally, we report on the relation between the convergence time of the model and the size of the instances of set covering.
Subjects / Keywords
Set covering