2026-08-07T11:39:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12044 2024-03-06T10:49:15Z ddc:004 open_access

Diffusion Limits in the Online Subsequence Selection Problems Gnedin, Alexander Seksenbayev, Amirlan sequential optimisation longest increasing subsequence bin packing fluctuations in the selection process functional limit In the stochastic sequential optimisation problems it is of interest to study features of strategies more delicate than just their performance measure. In this talk we focus on variations of the online monotone subsequence and bin packing problems, where it is possible to give a fairly explicit asymptotic description of the selection processes under strategies that are sufficiently close to optimality. We show that the transversal fluctuations of the shape and the length of selected subsequence approach Gaussian functional limits that are very different from their counterparts in the offline problem, where the full set of data can be used in selection algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Gnedin and Amirlan Seksenbayev 2020 Is Part Of LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2020.14 urn:nbn:de:0030-drops-120444 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.14 eng https://creativecommons.org/licenses/by/3.0/legalcode