13 papers · ranked by Valyu relevance
Krasimir Yordzhev
Some randomized algorithms, used to obtain a random n 2 × n 2 Sudoku matrix, where n is a natural number, is reviewed in this study. Below is described the set Πn of all (2n) × n matrices, consisting of elements of the set Zn = {1, 2, . . . , n}, such that every row is a permutation. It is proved that such matrices…
James Aspnes
| | Table of contents | | | ii | | --- | --- | --- | --- | --- | | | List of figures | | | xiv | | | List of tables | | | xv | | | List of algorithms | | | xvi | | | Preface | | | xvii | | 1 | | Randomized algorithms | | 1 | | | 1.1 | A trivial example | | 2 | | | 1.2 | Verifying polynomial identities | | 3 | | | 1.3 |…
Michał Startek
This paper presents a novel algorithm solving the classic problem of generating a random sample of size s from population of size n with nonuniform probabilities. The sampling is done with replacement. The algorithm requires constant additional memory, and works in O(n) time (even when s >> n, in which case the…
Axel Bacher, Olivier Bodini, Alexandros Hollender, Jérémie Lumbroso
This article introduces an algorithm, MERGESHUFFLE, which is an extremely efficient algorithm to generate random permutations (or to randomly permute an existing array). It is easy to implement, runs in nlog2n + O(1) time, is in-place, uses nlog2n + Θ(n) random bits, and can be parallelized accross any number of…
Bruno Salezze Vieira, Eduardo Machado Silva, Antônio Augusto Chaves
Scheduling Authors: ['Bruno Salezze Vieira' 'Eduardo Machado Silva' 'Antônio Augusto Chaves'] Efficient surgery room scheduling is essential for hospital efficiency, patient satisfaction, and resource utilization. This study addresses this challenge by introducing a novel concept of Random-Key Optimizer (RKO)…
Nevin Brackett‐Rozinsky, Daniel Lemire
Pseudorandom values are often generated as 64-bit binary words. These random words need to be converted into ranged values without statistical bias. We present an efficient algorithm to generate multiple independent uniformlyrandom bounded integers from a single uniformly-random binary word, without any bias. In the…
Jiamin Wei, YangQuan Chen, Yongguang Yu, Yuquan Chen
L´evy flights is a random walk where the step-lengths have a probability distribution that is heavy-tailed. It has been shown that L´evy flights can maximize the efficiency of resource searching in uncertain environments, and also movements of many foragers and wandering animals have been shown to follow a L´evy…
Daniel Lemire
In simulations, probabilistic algorithms and statistical tests, we often generate random integers in an interval (e.g., [0,s)). For example, random integers in an interval are essential to the Fisher-Yates random shuffle. Consequently, popular languages like Java, Python, C++, Swift and Go include ranged random integer…
Manuel Penschuck
Shuffling is the process of rearranging a sequence of elements into a random order such that any permutation occurs with equal probability. It is an important building block in a plethora of techniques used in virtually all scientific areas. Consequently considerable work has been devoted to the design and…
Vaignana Spoorthy Ella
This paper investigates the use of different transformations for improving the randomness of sequences. In particular, convolutional codes are used for increasing the size of a given sequence and then a random mapping function is used for further randomization. We have shown how such a method can convert highly…
Vincent Cicirello
This report presents algorithms for generating small random samples without replacement. It considers two cases. It presents an algorithm for sampling a pair of distinct integers, and an algorithm for sampling a triple of distinct integers. The worstcase runtime of both algorithms is constant, while the worstcase…
Olga Ohrimenko, Michael T. Goodrich, Roberto Tamassia, Eli Upfal
One of the unmistakable recent trends in networked computation and distributed information management is that of cloud storage (e.g., see [15]), whereby users outsource data to external servers that manage and provide access to their data. Such services relieve users from the burden of backing up and having to maintain…
James A. Bellamy
Randomness of binary sequences has been studied for a long time [1] and it continues to interest researchers because of the need to distinguish (in applicable situations) between randomness that has a classical basis from randomness that emerges out of quantum behavior. Random binary sequences are important not only in…