Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 04, 2018, 12:15 pm
Duration: 45 minutes
Location: CAB G51
Speaker: Raphael Kübler
In my talk I will present a paper of A. Bernstein, J. Holm, and E. Rotenberg published in 2018.
In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. In their paper they show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized O(log²n) replacements per insertion, where n is the total number of vertices inserted.
Automatic MiSe System Software Version 1.4803M | admin login