Cuts and Flows in Directed Graphs
Sanjeev Khanna
Department of Computer and Information Science
University of Pennsylvania
Wednesday, February 7, 2007
4:30 - 5:30 PM
Terman Engineering Center, Room 453
Abstract:
Cuts and flows are among the most well-studied concepts in
combinatorial optimization. The duality between cuts and flows
plays a central role in many algorithms. The performance of several
algorithms is tied to the flow-cut gap: the worst-case ratio between
multicommodity flow and multicut.
The flow-cut gap in undirected graphs is well-understood, and is known
to be \Theta(log n). However, so far, the question of flow-cut gap in
directed graphs has remained wide open. The best known lower
bound is logarithmic while the best known upper bound is polynomial.
In a sharp contrast to the undirected case, we will show in this talk
that the flow-cut gap in directed graphs can be polynomially large.
Based on our flow-cut gap construction, we will also briefly describe
a strong hardness of approximation result for the directed multicut and
the directed sparsest cut problem.
This is joint work with Julia Chuzhoy (IAS).
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html