Counting with Combined Splitting and Capture-Recapture Methods

We apply the splitting method to three well-known counting problems, namely 3-SAT, random graphs with prescribed degrees, and binary contingency tables. We present an enhanced version of the splitting method based on the capture-recapture technique, and show by experiments the superiority of this technique for SAT problems in terms of variance of the associated estimators, and speed of the algorithms.

MoreLess

Year of publication:	2011
Authors:	Dupuis, Paul ; Kaynar, Bahar ; Ridder, Ad ; Rubinstein, Reuven ; Vaisman, Radislav
Publisher:	Amsterdam and Rotterdam : Tinbergen Institute
Subject:	Stichprobenverfahren \| Algorithmus \| Theorie \| Counting \| Gibbs Sampler \| Capture-Recapture \| Splitting

More details

Series:	Tinbergen Institute Discussion Paper ; 11-062/4
Type of publication:	Book / Working Paper
Type of publication (narrower categories):	Working Paper
Language:	English
Other identifiers:	840694342 [GVK] hdl:10419/86914 [Handle] RePEc:dgr:uvatin:20110062 [RePEc]
Classification:	C15 - Statistical Simulation Methods; Monte Carlo Methods ; C63 - Computational Techniques
Source:	EconStor

Persistent link: https://ebvufind01.dmz1.zbw.eu/10010325899