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 条
  • [21] RECURRENT SELECTION FOR INCREASING SEED SIZE IN MAIZE
    GRITTI, O
    BERTOLINI, M
    MOTTO, M
    MAYDICA, 1994, 39 (02): : 149 - 154
  • [22] On Two Variants of the Longest Increasing Subsequence Problem
    Deorowicz, Sebastian
    Grabowski, Szymon
    MAN-MACHINE INTERACTIONS, 2009, 59 : 541 - +
  • [23] The Merged Longest Common Increasing Subsequence Problem
    Lee, Chien-Ting
    Yang, Chang-Biau
    Huang, Kuo-Si
    RECENT CHALLENGES IN INTELLIGENT INFORMATION AND DATABASE SYSTEMS, ACIIDS 2024, PT I, 2024, 2144 : 202 - 212
  • [24] Improved Dynamic Algorithms for Longest Increasing Subsequence
    Kociumaka, Tomasz
    Seddighin, Saeed
    STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2021, : 640 - 653
  • [25] AN ALGORITHM FOR THE DETERMINATION OF A LONGEST INCREASING SUBSEQUENCE IN A SEQUENCE
    ORLOWSKI, M
    PACHTER, M
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1989, 17 (07) : 1073 - 1075
  • [26] Fast computation of a longest increasing subsequence and application
    Crochemore, Maxime
    Porat, Ely
    INFORMATION AND COMPUTATION, 2010, 208 (09) : 1054 - 1059
  • [27] Reducing the number of specified values per test vector by increasing the test set size
    Pomeranz, I
    Reddy, SM
    IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES, 2006, 153 (01): : 39 - 46
  • [28] 5 GENERATIONS OF SELECTION FOR INCREASING LITTER SIZE IN SWINE
    OLLIVIER, L
    GENETICS, 1973, 74 (JUN) : S202 - S203
  • [29] Online construction of subsequence automata for multiple texts
    Hoshino, H
    Shinohara, A
    Takeda, M
    Arikawa, S
    SPIRE 2000: SEVENTH INTERNATIONAL SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL - PROCEEDINGS, 2000, : 146 - 152
  • [30] An adaptive O(log n)-optimal policy for the online selection of a monotone subsequence from a random sample
    Arlotto, Alessandro
    Wei, Yehua
    Xie, Xinchang
    RANDOM STRUCTURES & ALGORITHMS, 2018, 52 (01) : 41 - 53
12345