Zur Seite der TU
Zur Seite des Instituts für Mathematik
Zur Seite der BMS

Seminar: Computing Optimal Steiner Trees in Graphs

 

Winter-Semester 2017

 
LV-Nr.: 3236 L 380
 
Prof. Dr. Thorsten Koch
 




Contents

This seminar deals with methods to compute optimal Steiner trees in graphs and variants thereof. We will focus on practical solving methods and will in particular review 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, October 11, 2017 at 10:00 h ct in room MA 550 at TU.

The kickoff, where every participant will give an overview (of at most five minutes) on their topic, will take place on
Thursday, November 23, 2017, 09:30-10:30 at Zuse Institute Berlin, room 3028

Finally, the main talks will be held on
Thursday, February 1, 2018, 10:00-16:00 at Zuse Institute Berlin, room 3028



Dates and rooms are subject to change. Further dates will be appointed if neccessary.

Schedule

The Steiner tree problem I: Formulations, compositions and extension of facets

A comparison of Steiner tree relaxations

Approaches to the Steiner Problem in Networks

Improving Linear Programming Approaches for the Steiner Tree Problem

Practical partitioning-based methods for the Steiner problem

Extending Reduction Techniques for the Steiner Tree Problem: A Combination of Alternative and Bound-Based Approaches

Thinning out Steiner trees: a node-based model for uniform edge costs

A Robust and Scalable Algorithm for the Steiner Problem in Graphs

Local search heuristics for hop-constrained directed Steiner tree problem


Registration

Students interested in participating in the seminar are invited to come to the initial meeting. For additional information please contact Thorsten Koch (koch at zib.de) or Daniel Rehfeldt (rehfeldt 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





Last change: 27th March 2016