Randomized Rounding
l
Convert fractional to integral solutions
l
Get approximation algorithms for integer
programs
l
“Sampling” from a well designed sample
space of feasible solutions
l
Good approximations for network
design.