Multisampling: A New Approach to Uniform Sampling and Approximate Counting
Lists
Only you see this
Abstract
In this paper we present a new approach to uniform sampling and approximate counting. The presented method is called multisampling and is a generalization of the importance sampling technique. It has the same advantage as importance sampling, it is unbiased, but in contrary to it’s prototype it is also an almost uniform sampler. The approach seams to be as universal as Markov Chain Monte Carlo approach, but simpler. Here we report very promising test results of using multisampling to the following problems: counting matchings in graphs, counting colorings of graphs, counting independent sets in graphs, counting solutions to knapsack problem, counting elements in graph matroids and computing the partition function of the Ising model.
BibTeX
@inproceedings{sankowski2003multisampling,
author = {Piotr Sankowski},
title = {{Multisampling: A New Approach to Uniform Sampling and Approximate Counting}},
booktitle = {ESA},
year = {2003},
url = {https://openreview.net/forum?id=lQ4djKJaqh},
}Loading related content...