Abstract:
We will discuss how one can use randomized rounding to systematically derive primal-dual algorithms --- particularly greedy algorithms and Lagrangian-relaxation algorithms --- for approximately solving packing and covering problems such as set cover, vertex cover, and multi-commodity flow. The talk should be of interest to those interested in probabilistic methods and to those interested in approximation algorithms for combinatorial optimization problems.