ICE-TCS seminar: Christian Konrad
Date/Time: Friday, 13 May 2016, from 12:15 - 13:00
Location: M1.22 - Reykjavík University
Speaker: Christian Konrad (Reykjavik University)
Title: On the Power of Advice and Randomization for Online Bipartite Matching
An online algorithm receives its input piece-by-piece in a serial fashion. Upon reception of a piece of the input, it has to irrevocably decide how to process this piece of data. Since the online algorithm can base its decisions only on what it has seen in the past, and, in particular, has no information about future, it is often difficult or impossible to take good decisions. For many problems, access to randomness helps to avoid that the algorithm always takes the wrong decisions.
Suppose that we provide the online algorithm with additional knowledge about the future (= advice). Clearly, if enough information is given, we can obtain optimal solutions. However, does it help if we grant only very few advise bits to the algorithm? How many advise bits are needed to outperform any randomized online algorithm? In this work, we study these questions with regards to the maximum bipartite matching problem.
This is joint work with Christoph Dürr (Université Pierre et Marie Curie, Paris) and Marc Renault (Université Paris Diderot, Paris).