Randomized rounding Example: max weighted sat ILP formulation Rounding algorithm Approximation Multi-cut and multi-commodity flow problems Min multi-cut problems ILP formulation of min multi-cut Dual formulation max multi-commodity flow Alternative formulation of max multi-commodity flow Find a fast approximate solution to the LP formulation An O(log k) approximation for min multi-cut Pipe-Cut (Gi,x) A ball of radius r Find the right radius Conclusions Fast approximation for fractional packing and covering The dual problem The algorithm The analysis 1 The analysis 2
