Paper Info
Title
Exploration of NP-hard enumeration problems by simulated annealing—the spectrum values of permanents
Abstract
The Monte Carlo optimisation technique simulated annealing has been used to sample the possible values of the permanent of fully indecomposable (0,1)-matrices. The basic idea in simulated annealing is that a Markov chain explores the space of feasible solutions, each of which has an associated “energy” (here minus the permanent of the matrix). The control parameter “temperature” is gradually reduced in order to focus the search on the low-energy region of state space and eventually reaching the minimum. Although the minimum energy per se (largest permanent) is known, the spectrum above the minimum is not, so this importance sampling technique is quite efficient. Interest in permanents is based on the fact that it is “complete” for the class # P of enumeration problems, that is as hard as counting the number of accepting computations of any nondeterministic polynomial time Turing machine. The spectrum of possible values for the permanent of a (0, 1)-matrix with given topological dimension d is quite interesting but only partially understood. The present work is an experimental study of this spectrum using the handle basis representation of directed graphs and simulated annealing to sample the possible values. The results show that gaps exist in the spectrum of values of the permanent but also show the existence of values for d = 8 and 9 not hitherto observed. The new values in the spectrum of the permanent for d = 8 is 72 and for d = 9 are 119, 132, 136, 138, and 140. Further we found that the density of states grows exponentially with the permanent values. The larger the value of the permanent the larger the number of neighbours and the larger the energy barriers between the permanent values of the neighbours.
Year
DOI
Venue
1999
10.1016/S0304-3975(99)80002-4
Theor. Comput. Sci.
Keywords
DocType
Volume
importance sampling,NP-hard enumeration problem,spectrum value,Permanents,handle basis representation,#p hard enumeration,permanents,simulated annealing,Importance sampling,Handle basis representation,# P hard enumeration,Simulated annealing
Journal
215
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
4
PageRank 
References 
Authors
0.49
6
2
Name
Order
Citations
PageRank
Yaghout Nourani140.49
Bjarne Andresen242.52