Computer Science/Discrete Mathematics Seminar II

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 focus on several well-known cut problems in graphs, including multicut and sparsest cut. We will survey some existing algorithmic techniques and also present some new 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 undirected graphs, where the gap is known to be only logarithmic. Based on joint work with Sanjeev Khanna.