• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

A neural network for the minimum set covering problem

Thumbnail
Date
2000
Dewey
Recherche opérationnelle
Sujet
Set covering
Journal issue
Chaos, Solitons and Fractals
Volume
11
Number
13
Publication date
10-2000
Article pages
2079-2089
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/S0960-0779(99)00104-6
URI
https://basepub.dauphine.fr/handle/123456789/3689
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Zissimopoulos, Vassilis
Paschos, Vangelis
Hifi, Mhand
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.