Theory Lunch

TIME:: Wednesday, Oct. 24, noon till 1pm

PLACE:: 7220 Wean Hall

TITLE::  "Approximating Directed Multicuts", 
         by J. Cheriyan, H. Karloff, Y. Rabani (FOCS 2001)

SPEAKER::  Jochen  Könemann


The seminal paper of Leighton and Rao (1988) and subsequent papers
presented approximate min-max theorems relating multicommodity flow
values and cut capacities in undirected networks, developed the
divide and conquer method for designing approximation algorithms,
and generated tools for utilizing linear programming. relaxations.
Yet, despite persistent research efforts, these relaxations could
not be extended to directed networks, excluding a few cases that
are "symmetric" and therefore similar to undirected networks. The
paper is an attempt to remedy the situation. The authors consider
the problem of finding a minimum multicut in a directed multicommodity
flow network, and give the first non-trivial upper bounds on the
max-flow-to-min-multicut ratio. The results are algorithmic,
demonstrating non-trivial approximation guarantees.

Paper available at