arXiv (Cornell University) · 2013 · 18 citations · 17 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsComputational GeometryGraph AlgorithmsGraph LabelingGraph TheoryMarkov Chain Monte CarloSampling TechniquesSampling TheoryEnumerative Graph TheoryGraph EnumerationRandom Graph TheoryRandom SamplingRandom Sampling Algorithms
Sampling from combinatorial families can be difficult. However, complicated families can often be embedded within larger, simpler ones, for which easy sampling algorithms are known. We take advantage of such a relationship to describe a sampling algorithm for the smaller family, via a Markov chain started at a random sample of the larger family. The utility of the method is demonstrated via several examples, with particular emphasis on sampling labelled graphs with given degree sequence, a well-studied problem for which existing algorithms leave much room for improvement. For graphs with given degrees, with maximum degree $O(m^{1/4})$ where $m$ is the number of edges, we obtain an asymptotically uniform sample in $O(m)$ steps, which substantially improves upon existing algorithms.
17
Simulated Tempering: A New Monte Carlo Scheme
Enzo Marinari, Giorgio Parisi · Europhysics Letters (EPL) · 1992 · 1.9K citations · Full text
Mark Jerrum, Alistair Sinclair · SIAM Journal on Computing · 1989 · 793 citations