Graduate Seminar on Discrete Optimization

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:

One may consider only a specified class of graphs, e.g. planar or Eulerian graphs.
We can allow fractional solutions, so we rather ask for multicommodity flows than for disjoint paths.
We may want to choose only a subset of the terminals to be connected, so we want to maximize the number (or the weight) of the terminals that can be connected instead of just deciding if all of them can be connected.
One may allow a congestion on the edges of G, so one may violate the capacity constraints e.g. by a constant factor.

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

A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
Each participant has to write a summary consisting of one or two pages.
Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.

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