On the advice complexity of online bipartite matching and online stable marriage

摘要

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, [log_2(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.