Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


Monday Lecture and Colloquium


Monday, November 09, 2015

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
roomMA 041



Lecture - 14:15

Alex Fink - Queen Mary University of London


Matroids over rings

Abstract:
Matroids arise in many algebra-flavoured combinatorial problems which feature lists of vectors over a field. But often one's data are elements in a module over some other ring, and there is more information to be extracted than the field-agnostic linear algebra that the matroid can see. Luca Moci and I have defined the notion of _matroid over a ring_ to expose this extra information.

I will begin by reviewing matroids and introducing matroids over rings. I'll discuss two examples of situations where matroids leave some combinatorics uncaptured that the theory over rings does take in, one related to subtorus arrangements and the other to tropical geometry. Further topics will include their analogue of the Tutte polynomial, matroid polytopes, and their moduli space, as time permits.



Colloquium - 16:00

Aaron Bernstein - Columbia University


Fully Dynamic Matching with a Small Approximation Ratio -- Faster and Deterministic

Abstract:
We study the problem of maintaining an approximate maximum cardinality matching in an unweighted graph G that is subject to a sequence of insertions and deletions. The goal is recompute the approximate matching as quickly as possible after each insertion/deletion. Currently, there exist randomized algorithms with only polylog update time for maintaining a 2-or-worse approximate matching (e.g. a maximal matching), while the fastest update time for any algorithm that achieves a better-than-2 approximation is O(m^(1/2)). Intuitively the reason for this large gap is that maintaining a maximal (2-approximate) matching is a purely local problem in that as long as we match all legal edges, it does not matter which edges we choose: if both (u,v) and (u,w) are legal, either one can be chosen for the 2-approximate matching. To go beyond a 2-approximation, we need to keep track of some global structure in the graph, which is difficult to do in a dynamic setting.

In our paper, we set out to devise faster algorithms for maintaining a better-than-2 approximations. Our main result achieves an update time of m^(1/4) for a (3/2 + eps) approximation; the state of the art needs m^{1/2} update time, though it achieves a (1 + epsilon) approximation. Our algorithm achieves the fastest update time for a better-than-2 approximation, as well as the fastest existing deterministic update time for any constant approximation. Our approach also leads to some new results for small arboricity graphs. Our main technique is (loosely speaking) a new way of characterizing (1+eps) and (3/2+eps) approximate matchings -- one that does not rely on the non-existence of short augmenting paths.

This talk is based on two papers (ICALP 2015, SODA 2016), both joint work with Cliff Stein.