On the Power of Advice and Randomization for Online Bipartite Matching

摘要

While randomized online algorithms have access to a sequence of uniform random bits, deterministic online algorithms with advice have access to a sequence of advice bits, i.e., bits that are set by an all-powerful oracle prior to the processing of the req