Graduate Seminar on Discrete Optimization (S4C1)

Summer 2012


Integer Multiflows

In the edge-disjoint paths problems, we are given a (directed or undirected) graph G and ask for paths in G connecting given sets of terminal pairs such that the number of paths containing an edge e does not exceed its capacity. In general, problems of this type are NP-hard but there are several interesting ways to relax them:

In this graduate seminar, we will study recent publications that make use of such relaxations and present polynomial-time (exact or approximation) algorithms or show that the relaxations are still NP-hard. Moreover, we will consider graph theoretical aspects of these problems, e.g. we will compute the so-called flow-cut gap for different classes of graphs.


Class hours: Mondays 14:15-15:45. Approval talks: 12:15-13:45

Number Approval talk Talk Name Topic Mentoring
1 2.4
23.4. Simon Ahrens Cuts, trees and l1-embeddings of graphs Markus Struzyna
2 16.4
30.4. Lars Thorge Jensen Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums Markus Struzyna
3 23.4
7.5. Jannik Silvanus Coarse differentiation and multi-flows in planar graphs Jan Schneider
4 30.4
14.5. Clemens Rösner Embedding k-outerplanar graphs into l1 Jan Schneider
5 7.5
21.5. Christiane Engels Flow-cut gaps for integer and fractional multiflows Jan Schneider
6 14.5
4.6. Corinna Gottschalk Primal-dual approximation algorithms for integral flow and multicut in trees Michael Gester
7 21.5
11.6. Rudolf Scheifele Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems Michael Gester
8 4.6
18.6. Thomas Weyd Routing in undirected graphs with constant congestion Michael Gester
9 11.6
25.6. Maxime Wegesin Maximum edge-disjoint paths in planar graphs with congestion 2 Ulrike Suhl
10 18.6
2.7. Sonja Wittke Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs Ulrike Suhl

List of papers used for this seminar

Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.Prof. Dr. T. Nieberg,
Jun.Prof. Dr. S. Held,
Dr. U. Brenner