Séminaire du 25 septembre 06, Philippe Flajolet, Projet Algorithmes.
Boltzmann sampling and random generation of combinatorial structures
Boltzmann models, inspired from statistical physics,
amount to assigning to each object in a combinatorial class
a probability proportional to an exponential of its size.
We show here that such models can be used to derive efficient random generators
(or samplers), which can be built systematically from
formal specifications. The algorithms apply in both the labelled and unlabelled universe
and they can be tuned to target a certain size range. As a consequence,
one can often obtain approximate-size samplers of linear complexity
and exact size samplers of subquadratic complexity. Various applications to
words, trees, permutations, graphs, mappings, allocations,
partitions, and maps will be outlined. Structures with sizes in the range
between 10,000 and a million can be routinely generated in this way.
(Based on joint works with Philippe Duchon, Éric Fusy, Guy Louchard,
Carine Pivoteau, and Gilles Schaeffer).
Last modified: Mon May 23 18:32:54 CEST 2005