Node-weighted minimal Steiner trees logarithmic approximation

Speaker
Tomer Davidor and Ido Spector - BIU
Date
15/12/2015 - 11:30 - 10:30Add to Calendar 2015-12-15 10:30:00 2015-12-15 11:30:00 Node-weighted minimal Steiner trees logarithmic approximation 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  Math seminar room - building 216, room 201 אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Math seminar room - building 216, room 201
Abstract

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 

Last Updated Date : 08/12/2015