On the limitations of deterministic de-randomizations for online bipartite matching and max-sat

Nicolas Pena, Allan Borodin

The surprising results of Karp, Vazirani and Vazirani and (respectively) Buchbinder et al are examples where rather simple randomizations provide provably better approximations tha…