Non Uniform Generation of Combinatorial Objects

  • In this article we present a method to generate random objects from a large variety of combinatorial classes according to a given distribution. Given a description of the combinatorial class and a set of sample data our method will provide an algorithm that generates objects of size n in worst-case runtime O(n^2) (O(n log(n)) can be achieved at the cost of a higher average-case runtime), with the generated objects following a distribution that closely matches the distribution of the sample data.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Frank Weinberg, Markus Nebel
URN:urn:nbn:de:hbz:386-kluedo-16579
Series (Serial Number):Interner Bericht des Fachbereich Informatik (379)
Document Type:Report
Language of publication:English
Year of Completion:2010
Year of first Publication:2010
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2010/07/21
Faculties / Organisational entities:Kaiserslautern - Fachbereich Informatik
DDC-Cassification:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011