BARC/EADS talk by Chris Schwiegelshohn

On 21 September 2017, Chris Schwiegelshohn, postdoc at the university la Sapienza in Roma, will give a talk at DIKU.

Incremental Matching in Amortized Linear Time

We study the maximum cardinality matching problem in incremental graphs.

The edges of the graph arrive in some arbitrary order and at every given time, we would like to maintain a matching that is within some small constant factor of the current maximum matching. We present a deterministic algorithm for this problem whose total running time is linear in the size of the graph.


Portrait of SpeakerChris Schwiegelshohn is a postdoc at the university la Sapienza in Roma and did his PhD at the TU Dortmund. He is interested mainly in the design and analysis of algorithms, both with respect to running time and space requirements. For most of the problems he study, exact or optimal algorithms are not computationally feasible, which requires some degree of approximation. His work includes machine learning, clustering, streaming, and online algorithms. He also occasionally work on communication complexity lower bounds, especially in the context of single-pass streaming.