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 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