Algorithms and Complexity Seminar
Monday, December 4, 2006, 4-5:15pm in 32-G575.
Cut Problems in Graphs: Algorithms and Complexity
Julia Chuzhoy (IAS)
Cut problems are fundamental to combinatorial optimization, and they
naturally arise as intermediate problems in algorithm design. The study
of cut problems is inherently connected to the dual notion of flows. In
particular, starting with the celebrated max flow-min cut
theorem, flow-cut gaps have been extensively studied and are the basis
for many graph partitioning and routing algorithms.
In this talk we will investigate several well-known cut problems in
graphs, including multicut and sparsest cut. We will survey some
existing algorithmic techniques and present some recent hardness of
approximation results. In particular, we will show that the worst case
flow-cut gap in directed graphs is polynomial. This is in sharp
contrast to the undirected graphs, where the gap is known to be only
logarithmic.
Based on joint work with Sanjeev Khanna.
Host: Piotr Indyk
(The Algorithms
and Complexity Seminar series talks are usually held Mondays from
4-5:15pm in 32-G575.)