New answers tagged randomized-algorithms
1
vote
Accepted
What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?
I think there must be some confusion in the problem setting. Given an input of $n$ bits chosen uniformly at random, there is no algorithm to compress it to something whose length is on average ...

D.W.♦
- 156k
1
vote
Optimal randomized algorithm for set cover
Approximation ratio of 1 means that it outputs an exact solution (so it is not an approximation algorithm but rather an exact algorithm). Set cover is known to be NP-hard, so there is no such ...

D.W.♦
- 156k
Top 50 recent answers are included
Related Tags
randomized-algorithms × 425algorithms × 190
probability-theory × 74
complexity-theory × 55
algorithm-analysis × 51
randomness × 46
graphs × 36
probabilistic-algorithms × 26
time-complexity × 23
approximation × 20
runtime-analysis × 16
sorting × 16
sampling × 15
data-structures × 13
monte-carlo × 13
combinatorics × 12
pseudo-random-generators × 12
complexity-classes × 11
quicksort × 11
optimization × 10
streaming-algorithm × 10
terminology × 8
computational-geometry × 8
arrays × 8
random-number-generator × 8