Diffusion Limits in the Online Subsequence Selection Problems

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.