Résumé : The maximum expected length of increasing subsequence chosen by a real-time player from a random iid sequence is $\sqrt{2n}$, as was found by Samuels and Steele in 1981. In this talk we survey refinements and generalisations of this benchmark, also in connection with some bin-packing models.We further present recent results on fluctuations of the length and shape of the sequence selected by the optimal or a near-optimal policy.

 [Slides.pdf] [vidéo]

Dernière modification : Monday 27 May 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr