On the advice complexity of online bipartite matching and online stable marriage
We study the advice complexity of two online problems. The problems are online bipartite matching and online stable marriage. For both problems, we give exact advice complexity.
advice complexity bipartite matching stable marriage on-line algorithms