Approximating Graphs by Trees
March 4, 2009
At the STOC 2008 conference, Harry Raecke presented a result on approximating arbitrary capacitated flow networks by probability distributions over (capacitated) tree networks. His result is (somewhat surprisingly) based on another well-known result (of Bartal and Fakcharoenphol-Rao-Talwar) on approximating metrics by distributions over tree metrics. We present his result.

The talk here will be based on a presentation of Uri Feige.