Quickest online selection of an increasing subsequence of specified size

被引：5

作者：

Arlotto, Alessandro ^{[1
]}

Mossel, Elchanan ^{[2
]}

Steele, J. Michael ^{[3
]}

机构：

[1] Duke Univ, Fuqua Sch Business, 100 Fuqua Dr, Durham, NC 27708 USA

[2] Univ Penn, Dept Stat, Wharton Sch, Huntsman Hall 459, Philadelphia, PA 19104 USA

[3] Univ Penn, Wharton Sch, Dept Stat, Huntsman Hall 447, Philadelphia, PA 19104 USA

来源：

RANDOM STRUCTURES & ALGORITHMS | 2016年 / 49卷 / 02期

基金：

美国国家科学基金会;

关键词：

increasing subsequence problem; online selection; sequential selection; time-focused decision problem; dynamic programming; Markov decision problem; OPTIMAL SEQUENTIAL SELECTION; CENTRAL-LIMIT-THEOREM; MONOTONE SUBSEQUENCES; RANDOM-VARIABLES; SUM CONSTRAINT; RANDOM SAMPLE; LENGTH;

D O I：

10.1002/rsa.20634

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given a sequence of independent random variables with a common continuous distribution, we consider the online decision problem where one seeks to minimize the expected value of the time that is needed to complete the selection of a monotone increasing subsequence of a prespecified length n. This problem is dual to some online decision problems that have been considered earlier, and this dual problem has some notable advantages. In particular, the recursions and equations of optimality lead with relative ease to asymptotic formulas for mean and variance of the minimal selection time. (c) 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 235-252, 2016

引用

页码：235 / 252

页数：18

共 50 条

[1] Asymptotics and renewal approximation in the online selection of increasing subsequence
Gnedin, Alexander
Seksenbayev, Amirlan
BERNOULLI, 2021, 27 (03) : 1851 - 1869
[2] Sequential selection of an increasing subsequence from a sample of random size
Gnedin, AV
JOURNAL OF APPLIED PROBABILITY, 1999, 36 (04) : 1074 - 1085
[3] Online Scheduling with Increasing Subsequence Serving Constraint
Luo, Kelin
Xu, Yinfeng
Feng, Xin
Frontiers in Algorithmics, FAW 2016, 2016, 9711 : 135 - 144
[4] Diffusion approximations in the online increasing subsequence problem
Gnedin, Alexander
Seksenbayev, Amirlan
STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2021, 139 : 298 - 320
[5] Asymptotic Expansions and Strategies in the Online Increasing Subsequence Problem
Seksenbayev, Amirlan
ACTA APPLICANDAE MATHEMATICAE, 2021, 174 (01)
[6] Asymptotic Expansions and Strategies in the Online Increasing Subsequence Problem
Amirlan Seksenbayev
Acta Applicandae Mathematicae, 2021, 174
[7] QUICKEST CONVERGENCE OF ONLINE ALGORITHMS VIA DATA SELECTION
Romero, Daniel
Berberidis, Dimitris
Giannakis, Georgios B.
2016 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING PROCEEDINGS, 2016, : 6185 - 6189
[8] Optimal online selection of a monotone subsequence: a central limit theorem
Arlotto, Alessandro
Nguyen, Vinh V.
Steele, J. Michael
STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2015, 125 (09) : 3596 - 3622
[9] OPTIMAL ONLINE SELECTION OF AN ALTERNATING SUBSEQUENCE: A CENTRAL LIMIT THEOREM
Arlotto, Alessandro
Steele, J. Michael
ADVANCES IN APPLIED PROBABILITY, 2014, 46 (02) : 536 - 559
[10] Optimal online selection of an alternating subsequence: A central limit theorem
Fuqua School of Business, Duke University, 100 Fuqua Drive, Durham, NC 27708, United States
不详
Adv Appl Probab, 2 (536-559):

← 1 2 3 4 5 →