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
2000Journal name
Chaos, Solitons and FractalsVolume
11Number
13Publisher
Elsevier
Pages
2079-2089
Publication identifier
Metadata
Show full item recordAbstract (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 coveringRelated items
Showing items related by title and author.
-
Afif, Mohamed; Hifi, Mhand; Paschos, Vangelis; Zissimopoulos, Vassilis (1995) Article accepté pour publication ou publié
-
Zissimopoulos, Vassilis; Hifi, Mhand; Paschos, Vangelis (2004) Article accepté pour publication ou publié
-
Zissimopoulos, Vassilis; Paschos, Vangelis; Pekergin, Ferhan (1991) Communication / Conférence
-
Zissimopoulos, Vassilis; Paschos, Vangelis; Pekergin, Ferhan (1991) Article accepté pour publication ou publié
-
Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2010) Article accepté pour publication ou publié