MIT
119
Randomized Methods
lRandom
selection
»if most candidate choices “good”, then a random
choice is probably good
lMonte Carlo
simulation
»simulations estimate event likelihoods
lRandom
sampling
»generate a small random subproblem
»solve, extrapolate to whole problem
lRandomized
Rounding for approximation