An adaptive O(log n)‐optimal policy for the online selection of a monotone subsequence from a random sample

DOI10.1002/rsa.20728zbMath1387.60014arXiv1605.03998OpenAlexW2378499075WikidataQ92165919 ScholiaQ92165919MaRDI QIDQ4601440

Alessandro Arlotto, Yehua Wei, Xinchang Xie

Publication date: 16 January 2018

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.03998

zbMATH Keywords

dynamic programmingadaptive policyMarkov decision problemmonotone subsequenceonline selection

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Related Items (5)

Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards ⋮ Asymptotic expansions and strategies in the online increasing subsequence problem ⋮ The BRS-inequality and its applications ⋮ Asymptotics and renewal approximation in the online selection of increasing subsequence ⋮ Diffusion approximations in the online increasing subsequence problem

This page was built for publication: An adaptive O(log n)‐optimal policy for the online selection of a monotone subsequence from a random sample