Online Bipartite Matching under Markov Chain Model

Abstract

   Online bipartite matching (OBM) has a rich history in the literature of online algorithms, where it has been an influential problem inspiring many algorithms and techniques. This problem of obtaining a matching set of maximum size where vertices of one bi-partition arrive online has many real-world applications from kidney donor exchange to online advertising. This has led to the problem being studied under a variety of input models. In the adversarial model it is known that the tight competitive ratio is $1-1/e$ (among all randomized algorithms). Lower and upper bounds on competitive ratios better than $1-1/e$ are known for random order model, known and unknown IID models and other stochastic models, where a major open problem is to close these gaps.

One feature of the stochastic input models (e.g., known and unknown IID input models) under which OBM has been studied so far is the assumption of strong independence among the input items. One of the main conceptual contributions of this thesis is to introduce a stochastic input model that allows us to simulate limited dependence. In our model, input nodes are sampled from a Markov chain, and we refer to this as the Markov chain model. Introducing Markov chain significantly increases the complexity of analysis of algorithms by adding a number of parameters: initial distribution, transition probabilities, sampling size, etc, which leads us to concentrate on analyzing the problem for some specific families of bipartite graphs and Markov chains.

In particular, we study two algorithms \textsc{Non Adaptive} and \textsc{Adaptive Two Suggested Matching} under the Markov chain input model for parameterized versions of lazy random walks on $(2,2)$-biregular type graphs. We give an alternative characterization of an offline optimal solution, $OPT$, for these stochastic inputs, which allows us to calculate exactly (in the limit) the expected size of matching of $OPT$. We then proceed to obtain tight bounds on the sizes of matchings obtained by the two algorithms under asymptotic conditions, which combined with the bound on $OPT$, gives us tight competitive ratios of $0.9509$ and $0.9733$ for the \textsc{Non Adaptive} and \textsc{Adaptive} algorithms, respectively. These are competitive ratios for the classical lazy random walk Markov chain, where the probability of staying put is $1/2$. We also derive exact formulas for competitive ratios with respect to lazy walks parameterized by $p$ -- the probability of staying put.

We believe these results, which use two disjoint matchings and regularity of graph degrees could be extended to type graphs of degree at most $k$ (for any constant $k$), and to bipartite graphs that admit several disjoint matchings of large sizes.