1 Search Results for "Gnedin, Alexander"

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}
}

Refine by Author
1 Gnedin, Alexander
1 Seksenbayev, Amirlan

Refine by Classification
1 Mathematics of computing → Markov processes

Refine by Keyword
1 bin packing
1 fluctuations in the selection process
1 functional limit
1 longest increasing subsequence
1 sequential optimisation

Refine by Type
1 document

Refine by Publication Year
1 2020