License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2020.14
URN: urn:nbn:de:0030-drops-120444
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12044/
Go to the corresponding LIPIcs Volume Portal

Gnedin, Alexander ; Seksenbayev, Amirlan

Diffusion Limits in the Online Subsequence Selection Problems

pdf-format:
LIPIcs-AofA-2020-14.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{gnedin_et_al:LIPIcs:2020:12044,
  author =	{Alexander Gnedin and Amirlan Seksenbayev},
  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 =	{Michael Drmota and Clemens Heuberger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12044},
  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}
}

Keywords: sequential optimisation, longest increasing subsequence, bin packing, fluctuations in the selection process, functional limit
Collection: 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Issue Date: 2020
Date of publication: 10.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI