Graduate Seminar on Discrete Optimization (S4C1)

Summer 2025


Steiner Tree and Steiner Forest: LP Relaxations and Approximation Algorithms


Class hours: Mondays 14:15-15:45. Approval talks: 16:15-17:45

Slides from the plannng meeting with the list of talks
Number Approval Talk Talk Name Topic Mentoring
1 31.3. 14.4. Nora Depenheuer Prize-collecting Steiner tree, Steiner forest [GW (sec. 4.3), WS (sec. 5.7, ex. 14.5)] Antonia Ellerbrock
2 7.4. 28.4. Wendong Li On the integrality gap of the prize-collecting Steiner forest LP [KOPRSV] Antonia Ellerbrock
3 14.4. 5.5. Victoria Durán Fernández 2-approximation for prize-collecting Steiner forest [AGHJM1] Armin Settels
4 28.4. 12.5. Jofre Costa i Delgado 1.79-approximation for prize-collecting Steiner tree [AGHJM2] Armin Settels
5 5.5. 19.5. Niko Schmidt Bidirected cut relaxation for Steiner tree: lower bound (1) [V, sec. 1-2] Daniel Blankenburg
6 12.5. 26.5. Lennart Christian Grabbel Bidirected cut relaxation for Steiner tree: lower bound (2) [V, sec. 3] Daniel Blankenburg
7 19.5. 2.6. Lars Dominik Schmitz Bidirected cut relaxation for Steiner tree: upper bound (1) [BGT1, sec. 2-4.2] Susanne Armbruster
8 26.5. 16.6. Leo Diedering Bidirected cut relaxation for Steiner tree: upper bound (2) [BGT1, sec. 4.3-5] Susanne Armbruster
9 2.6. 23.6. Moritz Petrich On the bidirected cut relaxation for Steiner forest [BGT2] Paula Heinz
10 16.6. 30.6. Sergio Hernando Rivero Polylogarithmic inapproximability for directed Steiner tree [HK] Martin Drees
11 23.6. 7.7. Yuheng Shi Polylogarithmic approximation for group Steiner tree [GKR] Martin Drees


All discrete mathematics lecturers