• 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

On the approximation of NP-complete problems by using Boltzmann machine method. The cases of some covering and packing problems

Thumbnail
Date
1991
Dewey
Recherche opérationnelle
Sujet
NP-complete problems; Boltzmann machine method; combinatorial mathematics; computational complexity; heuristic programming
Conference name
International Conference on Novel Methods in Optimization
Conference date
02-1991
Conference city
Copenhague
Conference country
Danemark
URI
https://basepub.dauphine.fr/handle/123456789/5814
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Zissimopoulos, Vassilis
Paschos, Vangelis
Pekergin, Ferhan
Type
Communication / Conférence
Abstract (EN)
A Boltzmann machine architecture to solve the problems of maximum independent set, set partitioning, clique, minimum vertex cover, minimum set cover, and maximum set packing is described. The authors evaluate the maximum and the average error of the method where the error is defined as the ratio of the cardinality of the obtained solution for an instance with respect to the optimal one. The results are compared with those obtained from the implementation of the heuristic described by D.S. Johnson (1974). The model treats the general case of all these problems that is the case when costs are associated with the data (vertices or subsets). The unweighted case becomes a particular case in this approach. It is shown that the model finds optimal solutions for a large percentage of the treated instances and provides a good performance ratio for the rest.

  • 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.