Online Bipartite Matching in Offline Time (Abstract)

I will present our (with Bartłomiej Bosek, Dariusz Leniowski and Anna Zych) recent results on the problem of maintaining maximum size matchings in incremental bipartite graphs (FOCS’14). In this problem a bipartite graph

G

between

n

clients and

n

servers is revealed online. The clients arrive in an arbitrary order and request to be matched to a subset of servers. In our model we allow the clients to switch between servers and want to maximize the matching size between them, i.e., after a client arrives we find an augmenting path from a client to a free server. Our goals in this model are twofold. First, we want to minimize the number of times clients are reallocated between the servers. Second, we want to give fast algorithms that recompute such reallocation.

As for the number of changes, we propose a greedy algorithm that chooses an augmenting path

π

that minimizes the maximum number of times each server in

π

was used by augmenting paths so far. We show that in this algorithm each server has its client reassigned

$O(\sqrt{n})$

times. This gives an

O

(

n

3/2

) bound on the total number of changes, what gives a progres towards the main open question risen by Chaudhuri

et al.

(INFOCOM’09) who asked to prove

O

(

n

log

n

) upper bound. Next, we argue that the same bound holds in the decremental case. Moreover, we show incremental and decremental algorithms that maintain (1 − 

ε

)-approximate matching with total of

O

(

ε

− 1

n

) reallocations, for any

ε

 > 0.

Finally, we address the question of how to efficiently compute paths given by this greedy algorithm. We show that by introducing proper amortization we can obtain an incremental algorithm that maintains the maximum size matching in total

$O(\sqrt{n}m)$

time. This matches the running time of one of the fastest static maximum matching algorithms that was given by Hopcroft and Karp (SIAM J. Comput ’73). We extend our result to decremental case where we give the same total bound on the running time. Additionally, we show

O

(

ε

− 1

m

) time incremental and decremental algorithms that maintain (1 − 

ε

)-approximate matching for any

ε

 > 0. Observe that this bound matches the running time of the fastest approximate static solution as well.