Please note that this talk has beed rescheduled to * Wed, May 7th, 13:15 *.
Finding near-optimal Steiner Forests is a classic graph problem,
which arises in networks where one "purchases" (builds, rents,...) edges at
pre-defined costs and seeks to connect several subsets of the nodes. It is a
generalization of the well-known minimum spanning tree (MST) and Steiner
Tree problems, where additional intricacy is added by the fact that it may
or may not be beneficial to add connections between the different subsets
for the purpose of sharing purchased edges.
The goal of this talk is to show the beauty and elegance of the underlying
centralized techniques and their extensions to the distributed setting. We
will revisit old friends such as the algorithms by Kruskal, by Prim, and by
Bellman and Ford. On the way, we will see how the celebrated MST algorithm
of Galager, Humblet, and Spira arises naturally, as a parallelization of
Prim's algorithm. If time permits, I will give some insight into our recent
novel results on the topic, too. No previous knowledge beyond very basic
familiarity with graph algorithms will be assumed.
About the speaker:
Christoph Lenzen received a diploma in mathematics from the
University of Bonn, Germany, in 2007. In 2011, he received his Ph.D. in
Computer Science from ETH Zurich, which awarded his thesis with the ETH
medal. Subsequently, he spent two years as postdoctoral fellow in Israel, at
the Hebrew University of Jerusalem and the Weizmann Institute of Science.
Since 2013, he is a postdoctoral fellow at MIT. His research focuses on the
theory of distributed systems, covering, e.g., distributed graph algorithms,
fault-tolerance, and clock synchronization.
Last updated on 5 May 2014 by Antti Ukkonen - Page created on 28 Apr 2014 by Antti Ukkonen