Seminar: Discrete Optimization, Summer 2011


Prof. Dr. Martin Skutella

Type of Course:

Blockseminar; each student is supposed to give a presentation and prepare a written elaboration.

Time and Place


Based on selected articles or book chapters, we cover advanced topics in Discrete Optimization.


The seminar is intended for students in mathematics and "Techno-/Wirtschaftsmathematik". Profound knowledge of the courses ADM I and II is required. By agreement, Bachelor students can write their bachelor's thesis based on their presentation and written elaboration.

Participants & Topics:

Name Topic Advisor
Alice Zorn An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem Andreas Wiese
Felix Willamowski The VPN Problem with Concave Costs Martin Skutella
Julika Mehrgardt Beyond the Flow Decomposition Barrier Martin Groß
Michael Reinke A Combinatorial Problem Which Is Complete in Polynomial Space Madeleine Theile
Judith Simon Self-adjusting binary search trees Jan-Philipp Kappmeier
Max Richter A data structure for dynamic trees Wolfgang Welz
Julie Meißner Approximability of Robust Network Design José Verschae
Jana Barckmann Lifting valid inequalities for the precedence constrained knapsack problem Ashwin Arulselvan
Benjamin Müller Decomposition Approaches for a Capacitated Hub Problem Daniel Karch
Hannes Neumann Approximate extended formulations Olaf Maurer
Arne Müller Packing and Partitioning Orbitopes Andreas Bley
André Kühn Graph balancing: a special case of scheduling unrelated parallel machines Andreas Wiese
Agnes Cseh Balancing Minimum Spanning Trees and Shortest-Path Trees Jannik Matuschke
Andreas Schütz Approximating the Smallest k-edge Connected Spanning Subgraph by LP Rounding Martin Skutella
Hendrik Lüthen Efficient Algorithms for a Family of Matroid Intersection Problems Britta Peis