Seminar: Computing Optimal Steiner Trees in Graphs
|
LV-Nr.: 3236 L 380
Contents
This seminar deals with methods to compute optimal Steiner trees in graphs and variants thereof.
We will review the methods and
results of the
11th DIMACS Implementation Challenge: Steiner Tree Problems.
Broadly speaking, the goal of a Steiner tree problem is to find an optimal way (with respect to a specified criterion) of connecting a given set of objects. In most common variants, these objects are either points in a metric space or a subset of the vertices of a network.
Most of these problems are NP-hard, with the decision variant of the classic Steiner tree problem in graphs being one of Karp's famous 21 NP-complete problems, and real-world applications can be found for instance in
the design of large-scale computer circuits,
multicast routing in communication networks,
network optimization,
computer-aided design and
phylogenetic tree reconstruction.
Timing
The initial meeting of the seminar (Vorbesprechung), where the participants can select a topic/article, will take place on
Wednesday, April 20, 2016 at 10:00 h ct
in room MA 651 at TU.
The kickoff, where every participant will give an overview (of at most five minutes) on their topic, will take place on
Friday, May 13, 2016 at 10:00 h ct in room H 3012 at TU.
Finally, the main talks will be held on
June 30th at 11:15 at ZIB, lecture hall
and on July 1th at 10:00 at ZIB, lecture hall.
Dates and rooms are subject to change. Further dates will be appointed if neccessary.
Kickoff Schedule
Classical Steiner Problem in Graphs
1. RS - A Robust and Scalable Algorithm for the Steiner Problem in Graphs (Thomas Pajor, Eduardo Uchoa and Renato Werneck)
2. PN - Approximation Algorithms for Steiner Tree Problems Based on Universal Solution Frameworks
(Krzysztof Ciebiera, Piotr Sankowski, Piotr Godlewski and Piotr Wygocki)
3. TN - Dijkstra meets Steiner: Computational results of a fast exact Steiner tree algorithm (Stefan Hougardy, Jannik Silvanus and Jens Vygen)
Euclidean and Rectilinear Steiner Problem
4. FW - The GeoSteiner Software Package for Computing Steiner Trees in the
Plane: An Updated Computational Study (Daniel Juhl, David M. Warme, Pawel Winter and Martin Zachari-
asen)
5. TMN - Faster Exact Algorithms for Computing Steiner Trees in Higher Dimensional Euclidean Spaces
(Rasmus Fonseca, Marcus Brazil, Pawel Winter and Martin Zachariasen)
Prize-Collecting Variants
6. AR - Solving the Maximum-Weight Connected Subgraph Problem to Optimality (Mohammed El-Kebir and Gunnar W. Klau)
7. MS- Algorithms for the Maximum Weight Connected Subgraph and Prize-
collecting Steiner Tree Problems
(Ernst Althaus and Markus Blumenstock)
8. LE - A Fast, Adaptive Variant of the Goemans-Williamson Scheme for the
Prize-Collecting Steiner Tree Problem
(Chinmay Hegde, Piotr Indyk and Ludwig Schmidt)
Further Variants
9. JH - Local Search Heuristics for Hop-constrained Directed Steiner Tree
Problem
(Oleg Burdakov, Jonas Kvarnstrom and Patrick Doherty)
10. RR - Generalized local branching heuristics and the capacitated ring tree
problem
(Alessandro Hill and Stefan Voss)
11. MSE - A Heuristic Approach for the Stochastic Steiner Tree Problem (Pedro Hokama et al)
Registration
Students interested in participating in the seminar are invited to come to the
initial meeting. For additional informations please contact Thorsten Koch (koch at zib.de).
Seminar Requirements
Every participant is expected to attend all presentations of the seminar. Every
participant is also required to produce a handout of about five pages summarizing
the content of their own lecture. This handout is supposed to be produced in good
layout quality (some version of TeX is recommended). All handouts will be distributed
to all participants by e-mail before the seminar. All participants are free to
choose their own lecture style. Blackboards and a projector
will be available. The lectures should last about 30 minutes (45 including discussion). Basic knowledge
in Graph Theory and Linear and/or Integer Programming, such as taught in ADM I and
II, is a prerequisite for this seminar.
Further Information
This seminar is an Advanced Course of the Berlin Mathematical School (BMS).
A list of possible seminar papers can be found here.
Last change: 27th March 2016