Counting with combined splitting and capture-recapture methods

P. Dupuis, B. Kaynar, A.A.N. Ridder, R. Rubinstein, R. Vaisman

Research output: Contribution to JournalArticleAcademicpeer-review

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. © Taylor and Francis Group, LLC.
Original languageEnglish
Pages (from-to)478-502
JournalStochastic Models
Volume28
Issue number3
DOIs
Publication statusPublished - 2012

    Fingerprint

Cite this