In this talk, I will describe a family of randomized approximation
algorithms for several well-studied NP-hard network design problems.
These algorithms are extremely simple, and yet improve over the
previously best known approximation ratios, in some cases by orders
of magnitude. The analysis of these algorithms is driven by a novel
connection between approximation algorithms and cost sharing.

Joint work with Anupam Gupta (CMU), Amit Kumar (IIT Delhi), and
Martin Pal (Cornell).