Counting with Combined Splitting and Capture-Recapture Methods
Copyright policy )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.
25 pages
- Technion – Israel Institute of Technology Israel
- University of Queensland Australia
- School of Business and Economics, Econometrics and Operations Research Netherlands
- Brown University United States
- University of Amsterdam Netherlands
FOS: Computer and information sciences, Stichprobenverfahren, Counting, ddc:330, Capture Recapture Data, Probability (math.PR), 2611 Modelling and Simulation, Statistics - Computation, Gibbs Sampler, Algorithmus, Splitting, C63, 2604 Applied Mathematics, Counting, Gibbs Sampler, Capture-Recapture, Splitting, FOS: Mathematics, Capture-Recapture, C15, 2613 Statistics and Probability, Theorie, Mathematics - Probability, Computation (stat.CO), jel: jel:C63, jel: jel:C15
FOS: Computer and information sciences, Stichprobenverfahren, Counting, ddc:330, Capture Recapture Data, Probability (math.PR), 2611 Modelling and Simulation, Statistics - Computation, Gibbs Sampler, Algorithmus, Splitting, C63, 2604 Applied Mathematics, Counting, Gibbs Sampler, Capture-Recapture, Splitting, FOS: Mathematics, Capture-Recapture, C15, 2613 Statistics and Probability, Theorie, Mathematics - Probability, Computation (stat.CO), jel: jel:C63, jel: jel:C15
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!