OCTOBER 24, 2016
3:00 – 3:50 pm
CASS SCIENCE HALL ROOM 101
Refreshments to be served in Cass 312 after the talk

Title
New techniques for analysing online algorithms: matching theory to practice.

Speaker
Marc Renault , IRIF, Université Paris Diderot - Paris 7

Abstract: 
An algorithm is a set of instructions to process the input for a given problem. In the classical setting, algorithms have access to the entire input and the algorithm is a function applied to this input. The result of the function being the output. In contrast, in the online setting, the input is revealed sequentially, piece by piece; these pieces are called requests. Moreover, after receiving each request, the algorithm must take an action before the next request is revealed. That is, the algorithm must make irrevocable decisions based on the input revealed so far without any knowledge of the future input. Since the future is unknown, these decisions could prove very costly. Online problems have many real-world applications such as paging, routing and scheduling. In this talk, I'll introduce the topic of online computation, some classic online problems, and some techniques used to analyze online algorithms that have been developed over the last 30 years. Then, I'll show how our new techniques (the bijective ratio and approximate stochastic dominance) fit into this rich domain and apply them to classic problems with a particular focus on the greedy algorithm for the k-server problem, an algorithm that performs well in practice (on certain metric spaces) when the classic analysis tools claim it should not.
Refreshments will be served immediately after
in Cass Science Hall Resource Room 312

Hope to see you there on October 24, 2016!