Hostname: page-component-7c8c6479df-ph5wq Total loading time: 0 Render date: 2024-03-28T10:06:45.405Z Has data issue: false hasContentIssue false

Boltzmann Samplers for the Random Generation of Combinatorial Structures

Published online by Cambridge University Press:  24 September 2004

PHILIPPE DUCHON
Affiliation:
LaBRI, Université de Bordeaux I, 351 Cours de la Libération, F-33405 Talence Cedex, France (e-mail: duchon@labri.fr)
PHILIPPE FLAJOLET
Affiliation:
Algorithms Project, INRIA-Rocquencourt, F-78153 Le Chesnay, France (e-mail: Philippe.Flajolet@inria.fr)
GUY LOUCHARD
Affiliation:
Université Libre de Bruxelles, Département d'informatique, Boulevard du Triomphe, B-1050 Bruxelles, Belgique (e-mail: louchard@ulb.ac.be)
GILLES SCHAEFFER
Affiliation:
Laboratoire d'Informatique (LIX), École Polytechnique, 91128 Palaiseau Cedex, France (e-mail: Gilles.Schaeffer@lix.polytechnique.fr)

Abstract

This article proposes a surprisingly simple framework for the random generation of combinatorial configurations based on what we call Boltzmann models. The idea is to perform random generation of possibly complex structured objects by placing an appropriate measure spread over the whole of a combinatorial class – an object receives a probability essentially proportional to an exponential of its size. As demonstrated here, the resulting algorithms based on real-arithmetic operations often operate in linear time. They can be implemented easily, be analysed mathematically with great precision, and, when suitably tuned, tend to be very efficient in practice.

Type
Paper
Copyright
© 2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)