Questions tagged [sampling]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
10
votes
0answers
274 views

Finding uniformly random perfect matching of a graph

Problem: Suppose that we have a graph $ G $ which admits at least one perfect matching. I would like to know if there is an algorithm that allows to find any perfect matching of this graph uniformly ...
3
votes
0answers
82 views

Boltzmann sampling for containers/dependent polynomials?

I’d like to randomly sample from dependently-typed data structures. Has anyone looked at extending Boltzmann sampling to containers or dependent polynomials?
0
votes
0answers
82 views

Extension of a sampling Lemma of Indyk for $k$-median cost

A famous sampling lemma of Indyk (Theorem 31 here) states that if the $k$-median cost of a finite point set(in a metric space) is large with respect to the optimum, then this is true for the case of a ...
0
votes
0answers
84 views

Efficient sampling of primes

Using rejection sampling, it is trivial to construct a Las Vegas algorithm for sampling a uniformly random prime number less than a given $N$. What is known about sampling algorithms that run in worst-...