Events by date

Title: Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth

Abstract: I will present a recent max-flow min-cut type result for graphs of bounded treewidth. Multicommodity flow is a generalization of the well known s-t flow problem, where we are given multiple source-sink pairs and goal is to maximize the total flow. A natural upper bound on the value of total flow is the value of the minimum multicut : the minimum total capacity of edges that need to be removed in order to disconnect all the source-sink pairs. We will show that given a treewidth-r graph, there exists a (fractional) multi-commodity flow of value F, and a multicut of capacity C such that F ≤ C ≤ O(log r)·F.

Title: Kissing Polytopes

Abstract: We investigate the following question: how close can two disjoint lattice polytopes contained in a fixed hypercube be? This question stems from various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms.