Show simple item record

dc.contributor.authorZissimopoulos, Vassilis
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorPekergin, Ferhan
dc.date.accessioned2010-01-09T12:26:07Z
dc.date.available2010-01-09T12:26:07Z
dc.date.issued1991
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2843
dc.language.isoenen
dc.subjectheuristic programmingen
dc.subjectcomputational complexity;en
dc.subjectcombinatorial mathematicsen
dc.subjectBoltzmann machine methoden
dc.subjectNP-complete problemsen
dc.subject.ddc003en
dc.titleOn the approximation of NP-complete problems by using Boltzmann machine method: the cases of some covering and packing problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenA 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.en
dc.relation.isversionofjnlnameIEEE Transactions on Computers
dc.relation.isversionofjnlvol40en
dc.relation.isversionofjnlissue12en
dc.relation.isversionofjnldate1991-12
dc.relation.isversionofjnlpages1413-1418en
dc.relation.isversionofdoihttp://doi.ieeecomputersociety.org/10.1109/12.106226en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherIEEEen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record