Several real-world problems work in the 'online' setting where the input arrives in a sequential manner and decisions, sometimes irrevocable, need to be taken without access to the future inputs. In this thesis, we work on the online version of two problems: bipartite matching and facility location. In this synopsis, I'll present some of the results we obtained while studying the online bipartite matching problem.
The online bipartite matching problem is one of most classical online algorithms studied. Several real-life problems like organ donation, ad allocation etc can be formulated in terms of online bipartite matching. In their seminal work, Karp, Vazirani and Vazirani introduced the RANKING algorithm, a randomized algorithm which attained a competitive ratio of (1-1/e) for the unweighted case and showed that no randomized algorithm can do better. It is also known that the WATERLEVEL algorithm attains a similar competitive ratio for the deterministic fractional version of the unweighted problem. A lot of work has gone recently towards extending these algorithms to edge-weighted settings. In particular, a new sub-routine called online correlated selection (OCS) was introduced to achieve competitive ratio beyond the trivial 1/2 obtained by the greedy algorithm
In this work, we present the following results related to the online bipartite matching problem
- We show that for the degree-2 bounded case, where every online vertex has degree at most two, the folklore half-half algorithm achieves a competitive ratio of 0.717772 and more surprisingly show that this is in fact tight, no randomized algorithm can do any better
- We give a new OCS subroutine which attains the optimal parameter of 1/4. Previous results had shown that no OCS subroutine (even in the fully offline setting) can achieve a parameter better than 1/4.
- We give a deterministic WATERLEVEL-based algorithm that achieves a competitive ratio of (1-1/e) for the edge-weighted case. This result was known before, but to the best of our knowledge, this presentation in terms of water-level is new.
In the talk, I'll describe the bipartite matching problem, OCS problem, a summary of known results and an overview of the new algorithms that prove the above stated results.
