Spring 2017

Deterministic Isolation for Bipartite Matching and Matroid Intersection

Thursday, March 9th, 2017 11:00 am11:30 am

Add to Calendar


Calvin Lab Auditorium

We recently had a derandomization of the Isolation Lemma for perfect matchings in bipartite graphs and common base sets of two matroids. That is, a deterministic construction of an isolating weight assignment. The common idea in both the constructions is to work with their corresponding polytopes. In this talk, we present the approach in terms of general polytopes and describe sufficient conditions on the polytope for this approach to work. Finally, we argue that these conditions hold for bipartite matching polytope and common base set polytope.