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.
The talk here will be based on a presentation of Uri Feige.