Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/87255 
Erscheinungsjahr: 
2013
Schriftenreihe/Nr.: 
Tinbergen Institute Discussion Paper No. 13-122/III
Verlag: 
Tinbergen Institute, Amsterdam and Rotterdam
Zusammenfassung: 
In this paper we describe a Sequential Importance Sampling (SIS) procedure for counting the number of vertex covers in general graphs. The performance of SIS depends heavily on how close the SIS proposal distribution is to a uniform one over a suitably restricted set. The proposed algorithm introduces a probabilistic relaxation technique that uses Dynamic Programming in order to efficiently estimate this uniform distribution. The numerical experiments show that the scheme compares favorably with other existing methods. In particular the method is compared with cachet - an exact model counter, and the state of the art SampleSearch, which is based on Belief Networks and importance sampling.
Schlagwörter: 
Vertex Cover
Counting problem
Sequential importance sampling
Dynamic Programming
Relaxation
Random Graphs
JEL: 
C61
C63
Dokumentart: 
Working Paper
Erscheint in der Sammlung:

Datei(en):
Datei
Größe
200.19 kB





Publikationen in EconStor sind urheberrechtlich geschützt.