1 Search Results for "Seksenbayev, Amirlan"


Document
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

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail