N&O Lecture Matthias Mnich: New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness

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.
  • N&O Lecture Matthias Mnich: New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness
  • 2016-11-30T10:00:00+01:00
  • 2016-11-30T11:00:00+01:00
  • 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.
  • When Nov 30, 2016 from 10:00 AM to 11:00 AM (Europe/Amsterdam / UTC100)
  • Where Room L120, first floor CWI, Science Park 123 Amsterdam
  • Web Visit external website
  • Add event to calendar iCal

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).