Viðburðir eftir árum

ICE-TCS Seminar: Allan Borodin (University of Toronto)

Online bipartite matching revisited

  • 9.11.2017, 11:00 - 12:00


ICE-TCS Seminar

Allan Borodin (University of Toronto)

When: Thursday the 9th of November at 11:00
Where: M102

Title: Online bipartite matching revisited

Abstract: The seminal Karp, Vazirani and Vazirani (KVV) results on biparite matching provide a definitive analysis of the competitive ratio for deterministic and randomized online algorithms for bipartite matching. Namely, that no deterministic (respectively, randomized) online algorithm can provide a ratio better than 1/2 (resp, 1-1/e). These results are with respect to the traditional one pass online model. We revisit this problem in the context of more permissive models that extend the online model. More generally, when and how can we de-randomize an online algorithm.

Hope to see you there

On behalf of ICE-TCS

Eyjólfur Ingi Ásgeirsson