On Maintaining Online Bipartite Matchings with Augmentations
Dariusz Leniowski · 2015
In this thesis we study the setting of online bipartite matchings with augmentations, in which a bipartite graph G = 〈U] V ,E〉 is revealed online in a one-sided vertex-incremental fashion. In other words, the set U is known from the start, while the vertices of V arrive one by one, each together with all its incident edges. Our goal is to maintain the maximum cardinality matching, in particular, the previous decisions are revocable. Nevertheless, although we are allowed to reassign already matched pairs to accommodate the newly arrived vertices, as far as it is possible, we would like to keep the number of such operations low. We approach this problem using two greedy strategies, both based on the classical augmenting paths technique. First, we investigate the shortest augmenting path algorithm, which each turn augments the current matching by using shortest augmenting paths. It was conjectured that the total length of all such paths is O ( n logn ) , but no better bound than the naive O ( n ) is known even for trees. In this setting we prove an O ( n log n ) upper bound when the underlying graph G is a tree. For the case of general bipartite graphs we propose another greedy strategy that tries to minimize the maximum number of times each vertex of U is used by augmenting paths so far. This approach yields a new algorithm that produces augmenting paths that reassign any vertex of U at most O ( n/2 ) times, implying an upper bound of O ( n/2 ) on the total length of augmenting paths. We show how to efficiently compute these paths and describe an algorithm that maintains the maximum cardinality matching in O ( m ·n/2 ) total time and a (1− e)-approximation algorithm that works in O ( m · e−1 ) time. Moreover, we extend these results to the decremental case where we give the same total bound. Furthermore, we obtain a pseudo-polynomial algorithm for weighted graphs. Finally, we provide examples demonstrating that our analysis is tight.