Ground-State Entropy of the Random Vertex-Cover Problem

Details Ground-State Entropy of the Random Vertex-Cover Problem Ground-State Entropy of the Random Vertex-Cover Problem

2008-10-03

arxiv.org/abs/0810.0584v2

Physical Review E 79, 020103 (R) (2009)

Physics

Condensed Matter

Disordered Systems and Neural Networks

4 pages, 2 figures. Final version as appear in PRE

Scientific paper

10.1103/PhysRevE.79.020103

Counting the number of ground states for a spin-glass or NP-complete combinatorial optimization problem is even more difficult than the already hard task of finding a single ground state. In this paper the entropy of minimum vertex-covers of random graphs is estimated through a set of iterative equations based on the cavity method of statistical mechanics. During the iteration both the cavity entropy contributions and cavity magnetizations for each vertex are updated. This approach overcomes the difficulty of iterative divergence encountered in the zero temperature first-step replica-symmetry-breaking (1RSB) spin-glass theory. It is still applicable when the 1RSB mean-field theory is no longer stable. The method can be extended to compute the entropies of ground-states and metastable minimal-energy states for other random-graph spin-glass systems.

Affiliated with

Also associated with

No associations

Rating

Ground-State Entropy of the Random Vertex-Cover Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Ground-State Entropy of the Random Vertex-Cover Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ground-State Entropy of the Random Vertex-Cover Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-409522