Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 11 mai 2021 à 10h00 en visioconférence, Alexander Gnedin nous parlera de : Online selection of long increasing subsequences and related problems (joint seminar with LAGA)

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 : Thursday 21 November 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr