Title: Online Matroid Intersection: Beating Half for Random Arrival
| Speaker: | Jacob Skitsko |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: We'll take a gander at the paper Online Matroid Intersection: Beating Half for Random Arrival by Guruganesh and Singla. We're given two matroids defined on elements of a common ground set, and elements will arrive one-by-one in a uniformly random order. Whenever an element arrives we'll need to decide to keep them or tell them goodbye forever. The greedy algorithm gives us a competitive ratio of 1/2, but can we do better? Yes! (Slightly, with a simple randomized algorithm). We'll first take a look at the special case of bipartite matching. The results also extend in a natural way to the intersection of k matroids, and non-bipartite matching. If I don't ramble too much, we'll also get to (briefly) discuss a recent improvement for the intersection of 2 matroids.