Node-weighted minimal Steiner trees logarithmic approximation
Seminar
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
