12 papers · ranked by Valyu relevance
Krasimir Yordzhev
The paper considers implementations of some randomized algorithms in connection with obtaining a random n 2 × n 2 Sudoku matrix with programming language C++. For this purpose we describes 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.…
Matthias Volk, Borzoo Bonakdarpour, Joost-Pieter Katoen, Saba Aflaki
Randomization is a key concept in distributed computing to tackle impossibility results. This also holds for self-stabilization in anonymous networks where coin flips are often used to break symmetry. Although the use of randomization in self-stabilizing algorithms is rather common, it is unclear what the optimal coin…
Antoine Lhomme, Nicolas Catusse, Nadia Brauner
A frequently studied performance measure in online optimization is competitive analysis. It corresponds to the worst-case ratio, over all possible inputs of an algorithm, between the performance of the algorithm and the optimal offline performance. However, this analysis may be too pessimistic to give valuable insight…
Sander Borst, Daniel Dadush, Sophie Huiberts, Danish Kashaev
Explorable heap selection is the problem of selecting the nth smallest value in a binary heap. The key values can only be accessed by traversing through the underlying infinite binary tree, and the complexity of the algorithm is measured by the total distance traveled in the tree (each edge has unit cost). This problem…
Emin Karayel
Derandomization techniques are often used within advanced randomized algorithms. In particular, pseudorandom objects, such as hash families and expander graphs, are key components of such algorithms, but their verification presents a challenge. This work shows how such algorithms can be expressed and verified in…
Vincent Cicirello
Evolutionary algorithms rely very heavily on randomized behavior. Execution speed, therefore, depends strongly on how we implement randomness, such as our choice of pseudorandom number generator, or the algorithms used to map pseudorandom values to specific intervals or distributions. In this paper, we observe that the…
Mengqi Zhang, Guangqiang Teng, Xiaoyu Lei, Boris Ryabko
Lei proposed an algorithm Algorithm $A_{3}$ in 2023 to generate an exact discrete uniform distribution from an unknown biased Bernoulli source. The present paper does not claim a new extraction algorithm. Its contributions are analytical: first, we provide a Fourier-analytic proof of the uniformity mechanism based on…
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…
Allan Borodin, Christodoulos Karavasilis, David Zhang
Interest in the random order model (ROM) leads us to initiate a study of utilizing random-order arrivals to extract random bits with the goal of de-randomizing algorithms. Besides producing simple algorithms, simulating random bits through random arrivals enhances our understanding of the comparative strength of…
Yongxin Li
This work starts from definition of randomness, the results of algorithmic randomness are analyzed from the perspective of application. Then, the source and nature of randomness is explored, and the relationship between infinity and randomness is found. The properties of randomness are summarized from the perspective…
Oleksandr Sverdlov, Yevgen Ryeznik, Volodymyr Anisimov, Olga M. Kuznetsova + 4 more
'Olga M. Kuznetsova' 'Ruth Knight' 'Kerstine Carter' 'Sonja Drescher' 'Wenle Zhao'] Background The design of a multi-center randomized controlled trial (RCT) involves multiple considerations, such as the choice of the sample size, the number of centers and their geographic location, the strategy for recruitment of…
Abdul Kader Kassoumeh, Zühal Kartal, Ahmet Arslan, Dragan Pamucar
This article introduces methods for initializing a single-trajectory-based metaheuristic, specifically a simulated annealing (SA) algorithm, using constructive heuristics. These methods are designed to target promising regions within the search space of an nondeterministic polynomial time (NP)-hard problem, namely the…