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.

In this paper, we study the advice complexity of the online bipartite matching problem and the online stable marriage problem. We show that for both problems, ⌈log2⁡(n!)⌉⌈log2⁡(n!)⌉ bits of advice are necessary and sufficient for a deterministic online algorithm to be optimal, where n denotes the number of vertices in one bipartition in the former problem, and the number of men in the latter.