On Randomized Algorithms for Online Preemptive Matching

In this series of two talks, we will investigate the power of randomized algorithms for the maximum cardinality matching (MCM) and the maximum weight matching (MWM) problems in the online preemptive model. In this model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. When an edge is accepted, the edges adjacent to it are discarded. The goal is to construct as large (heavy) a matching as  possible.

The complexity of the problem is settled for deterministic algorithms. For randomized algorithms,  a lower bound of $1.693$ on the competitive ratio is known for MCM with a trivial upper bound of two;  an upper bound of $5.356$ is known for MWM. We initiate a systematic study of the same in this paper with an aim to isolate and understand the difficulty. We begin with  a primal-dual analysis of the deterministic algorithm due to McGregor. All deterministic lower bounds are on instances which are trees at  every step. Using a considerable extension of the (simple) primal-dual analysis of the deterministic case, we show a randomized algorithm that is $\frac{28}{15}$-competitive for this class of (unweighted) graphs.

In the first talk, we will review the background and earlier results. In the second talk, we will describe our randomized algorithm. We will also present other related results if time permits (based on joint work with Ashish Chiplunkar and Sundar Vishwanathan: http://arxiv.org/abs/1412.8615.)