Counting with combined splitting and capture-recapture methods

Dupuis, Paul, Kaynar, Baher, Ridder, Ad, Rubinstein, Reuven and Vaisman, Radislav (2012) Counting with combined splitting and capture-recapture methods. Stochastic Models, 28 3: 478-502. doi:10.1080/15326349.2012.699761

Author Dupuis, Paul
Kaynar, Baher
Ridder, Ad
Rubinstein, Reuven
Vaisman, Radislav
Title Counting with combined splitting and capture-recapture methods
Journal name Stochastic Models   Check publisher's open access policy
ISSN 1532-6349
Publication date 2012-07-01
Year available 2012
Sub-type Article (original research)
DOI 10.1080/15326349.2012.699761
Volume 28
Issue 3
Start page 478
End page 502
Total pages 25
Place of publication Philadelphia, PA United States
Publisher Taylor and Francis Inc.
Collection year 2013
Language eng
Subject 2611 Modelling and Simulation
2613 Statistics and Probability
2604 Applied Mathematics
Abstract 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.
Keyword Capture Recapture Data
Gibbs Sampler
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Fri, 07 Feb 2014, 10:18:34 EST by Radislav Vaisman on behalf of School of Mathematics & Physics