DocumentCode :
992814
Title :
On the approximation of NP-complete problems by using the Boltzmann machine method: the cases of some covering and packing problems
Author :
Zissimopoulos, V. ; Paschos, V. Th ; Pekergin, F.
Author_Institution :
Paris Univ., Orsay, France
Volume :
40
Issue :
12
fYear :
1991
fDate :
12/1/1991 12:00:00 AM
Firstpage :
1413
Lastpage :
1418
Abstract :
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
Keywords :
combinatorial mathematics; computational complexity; heuristic programming; neural nets; parallel architectures; Boltzmann machine method; NP-complete problems; approximation; clique; covering; maximum independent set; minimum set cover; minimum vertex cover; optimal solutions; packing problems; set partitioning; Approximation algorithms; Computer aided software engineering; Costs; Neural networks; Simulated annealing; Virtual colonoscopy;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.106226
Filename :
106226
Link To Document :
بازگشت