Dr. Marc Renault of Université Paris Diderot

Stochastic dominance is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. Accordingly this holds for bijective analysis, which can be interpreted as stochastic dominance assuming the uniform distribution over requests. These techniques have been applied in problems such as paging, list update, bin colouring, routing in array mesh networks, and in connection with Bloom filters, and have provided a clear separation between algorithms whose performance varies significantly in practice. However, despite their appealing properties, there are situations in which they are not readily applicable. This is due to the fact that they stipulate a stringent relation between the compared algorithms that may be either too difficult to establish analytically, or worse, may not even exist.

In this paper we propose remedies to both of these shortcomings. First, we establish sufficient conditions that allow us to prove the bijective optimality of a certain class of algorithms for a wide range of problems; we demonstrate this approach in the context of well-studied online problems such as weighted paging, reordering buffer management, and 2-server on the circle. Second, to account for situations in which two algorithms are incomparable or there is no clear optimum, we introduce the bijective ratio as a natural extension of (exact) bijective analysis. Our definition readily generalizes to stochastic dominance. This renders the concept of bijective analysis (and that of stochastic dominance) applicable to all online problems, is a broad generalization of the Max/Max ratio due to Ben-David and Borodin, and allows for the incorporation of other useful techniques such as amortized analysis. We demonstrate the applicability of the bijective ratio to one of the fundamental online problems, namely the continuous k-server problem on metrics such as the line, the circle, and the star. Among other results, we show that the greedy algorithm attains bijective ratios of O(k) consistently across these metrics. These results confirm extensive previous studies that gave evidence of the efficiency of this algorithm on said metrics in practice, which, however, is not reflected in competitive analysis.

Biography:

Marc Renault is currently a postdoc at IRIF, Université Paris Diderot - Paris 7 and a visiting researcher at LIP6, Université Pierre et Marie Curie (UPMC - Paris 6). Originally from Halifax, he obtained his Bachelor of Computer Science from Dalhousie University. He continued his studies at the Université Paris Diderot - Paris 7, where he received his Masters and PhD in Theoretical Computer Science under the supervision of Adi Rosén, studying online algorithms in the advice framework. Previously, he was a postdoc in the Operations Research group of LIP6 at the UPMC and a CNRS postdoc as part of the ERC Consolidator grant-funded project "Distributed Biological Algorithms" at IRIF, Paris 7. His research interests are in the design and analysis of algorithms, especially approximation algorithms, both online and offline, and, in particular, algorithms that move away from the conventional input-calculation-output scheme. These areas include online algorithms, search games, streaming algorithms, distributed computing, and algorithmic mechanism design.

Address:IRIF, Université Paris Diderot, Paris, France

Dr. Marc Renault of Université Paris Diderot

Biography:

Address:Paris, France