Skip to Main content Skip to Navigation
Conference papers

Random generation of combinatorial structures: Boltzmann samplers and beyond

Philippe Duchon 1, 2 
1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : The Boltzmann model for the random generation of ''decomposable'' combinatorial structures is a set of techniques that allows for efficient random sampling algorithms for a large class of families of discrete objects. The usual requirement of sampling uniformly from the set of objects of a given size is somehow relaxed, though uniformity among objects of each size is still ensured. Generating functions, rather than the enumeration sequences they are based on, are the crucial ingredient. We give a brief description of the general theory, as well as a number of newer developments.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00654267
Contributor : Philippe Duchon Connect in order to contact the contributor
Submitted on : Wednesday, December 21, 2011 - 2:21:07 PM
Last modification on : Saturday, June 25, 2022 - 8:29:48 PM
Long-term archiving on: : Thursday, March 22, 2012 - 2:26:49 AM

Files

Boltzmann_WSC11.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00654267, version 1
  • ARXIV : 1112.5071

Collections

Citation

Philippe Duchon. Random generation of combinatorial structures: Boltzmann samplers and beyond. Winter Simulation Conference, Dec 2011, Phoenix, United States. ⟨hal-00654267⟩

Share

Metrics

Record views

112

Files downloads

142