Random generation of combinatorial structures: Boltzmann samplers and beyond
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| dc.contributor.author | DUCHON, Philippe | |
| dc.contributor.editor | Jain | |
| dc.contributor.editor | S. and Creasey | |
| dc.contributor.editor | R.R. and Himmelspach | |
| dc.contributor.editor | J. and White | |
| dc.contributor.editor | K.P. and Fu | |
| dc.contributor.editor | M. | |
| dc.date.accessioned | 2024-04-15T09:45:57Z | |
| dc.date.available | 2024-04-15T09:45:57Z | |
| dc.date.issued | 2011-12-21 | |
| dc.date.conference | 2011-12-11 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197965 | |
| dc.description.abstract | Le modèle de Boltzmann pour la génération aléatoire de structures "décomposables" est un ensemble de techniques qui fournissent des algorithmes de tirage aléatoire pour une grande famille de classes d'objets discrets. L'exigence classique de génération uniforme parmi les objets d'une taille donnée est quelque peu relaxée, bien que l'équiprobabilité des objets de chaque taille soit préservée. Les séries génératrices, plutôt que les suites d'énumération sur lesquelles elles sont basées, sont l'ingrédient crucial. Nous donnons une brève description de la théorie générale, ainsi que quelques développements plus récents. | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.subject.en | Combinatorics | |
| dc.subject.en | Algorithms | |
| dc.subject.en | Random Sampling | |
| dc.title.en | Random generation of combinatorial structures: Boltzmann samplers and beyond | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| dc.subject.hal | Mathématiques [math]/Combinatoire [math.CO] | |
| dc.identifier.arxiv | 1112.5071 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | Winter Simulation Conference | |
| bordeaux.country | US | |
| bordeaux.conference.city | Phoenix | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00654267 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.end | 2011-12-14 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00654267v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2011-12-21&rft.au=DUCHON,%20Philippe&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||