Node-weighted minimal Steiner trees logarithmic approximation

Tue, 15/12/2015 - 10:30

In this lecture we present an improvement to the running time of the Philip Klein and R.Ravi approximation algorithm. The Philip-Klein algorithm produces a Steiner Tree that is close to the minimal one, by preforming iterations repeatedly. The iteration implementation is based on the distances between the nodes of the graph. The main hypothesis that led to our improvement is that there is no need to find all the distances in the graph but only a part of them. In addition, an example of the algorithm's implementation will be shown. 

Joint work with Eli Packer, IBM, and Shlomo Yanetz