Seminar: "Computing Optimal Steiner Trees in Graphs" (SS2016)

$Zur Seite der BMS$

Seminar: Computing Optimal Steiner Trees in Graphs

Sommer-Semester 2016

LV-Nr.: 3236 L 380

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