DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2020.14

Diffusion Limits in the Online Subsequence Selection Problems

Authors: Alexander Gnedin and Amirlan Seksenbayev

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract

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.

Cite as

Alexander Gnedin and Amirlan Seksenbayev. Diffusion Limits in the Online Subsequence Selection Problems. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gnedin_et_al:LIPIcs.AofA.2020.14,
  author =	{Gnedin, Alexander and Seksenbayev, Amirlan},
  title =	{{Diffusion Limits in the Online Subsequence Selection Problems}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.14},
  URN =		{urn:nbn:de:0030-drops-120444},
  doi =		{10.4230/LIPIcs.AofA.2020.14},
  annote =	{Keywords: sequential optimisation, longest increasing subsequence, bin packing, fluctuations in the selection process, functional limit}
}

Search Results

Documents authored by Gnedin, Alexander

Diffusion Limits in the Online Subsequence Selection Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message