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