We would like to announce the following lecture from Matthias Mnich (Bonn) at the N&O seminar:
Abstract:
We study the classical NP-hard problems of finding maximum-size subsets
from given sets of k terminal pairs that can be routed via edge-disjoint
paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The
approximability of MaxEDP/MaxNDP is currently not well understood; the
best known lower bound is \Omega(log^{1/2−ε}n), assuming NP
\not\subseteq ZPTIME(n^{polylog(n)}). This constitutes a significant gap
to the best known approximation upper bound of O(\sqrt(n)) due to
Chekuri et al. (2006), and closing this gap is currently one of the big
open problems in approximation algorithms. In their seminal paper,
Raghavan and Thompson (Combinatorica, 1987) introduce the technique of
randomized rounding for LPs; their technique gives an O(1)-approximation
when edges (or nodes) may be used by O(log(n)/loglog(n)) paths.
We strengthen these fundamental results. We provide new bounds
formulated in terms of the feedback vertex set number r of a graph,
which measures its vertex deletion distance to a forest. In particular,
we obtain
the following results:
– For MaxEDP, we give an O(\sqrt(r) * log(kr))-approximation algorithm.
Up to a logarithmic factor, our result strengthens the best known ratio
O(\sqrt(n)) due to Chekuri et al., as r \leq n.
– Further, we show how to route \Omega(OPT * ) pairs with congestion
bounded by O(logkr/loglogkr), strengthening the bound obtained by the
classic approach of Raghavan and Thompson.
(Joint work with Joachim Spoerhase and Krzysztof Fleszar).
