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.