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-04-07
Authors:	Dupuis, Paul ; Kaynar, Bahar ; Ridder, Ad ; Rubinstein, Reuven ; Vaisman, Radislav
Institutions:	Tinbergen Institute
Subject:	Counting \| Gibbs Sampler \| Capture-Recapture \| Splitting

freely available

Full text |

More access options

Check Google Scholar

In German libraries (KVK)

I need help

More details

Extent:	application/pdf
Series:	Tinbergen Institute Discussion Papers.
Type of publication:	Book / Working Paper
Notes:	The text is part of a series Tinbergen Institute Discussion Papers Number 11-062/4
Classification:	C15 - Statistical Simulation Methods; Monte Carlo Methods ; C63 - Computational Techniques
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10008916010