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 条
  • [31] Nearly Optimal Parallel Algorithms for Longest Increasing Subsequence
    Cao, Nairen
    Huang, Shang-En
    Su, Hsin-Hao
    PROCEEDINGS OF THE 35TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2023, 2023, : 249 - 259
  • [32] Longest Increasing Subsequence under Persistent Comparison Errors
    Geissmann, Barbara
    THEORY OF COMPUTING SYSTEMS, 2020, 64 (04) : 662 - 680
  • [33] Minimum Height and Sequence Constrained Longest Increasing Subsequence
    Tseng, Chiou-Ting
    Yang, Chang-Biau
    Ann, Hsing-Yen
    JOURNAL OF INTERNET TECHNOLOGY, 2009, 10 (02): : 173 - 178
  • [34] What Do a Longest Increasing Subsequence and a Longest Decreasing Subsequence Know about Each Other?
    Itskovich, Elizabeth J.
    Levit, Vadim E.
    ALGORITHMS, 2019, 12 (11)
  • [35] Longest Increasing Subsequence Computation over Streaming Sequences
    Li, Youhuan
    Zou, Lei
    Zhang, Huaming
    Zhao, Dongyan
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2018, 30 (06) : 1036 - 1049
  • [36] Efficient algorithms for finding a longest common increasing subsequence
    Chan, WT
    Zhang, Y
    Fung, SPY
    Ye, DS
    Zhu, H
    ALGORITHMS AND COMPUTATION, 2005, 3827 : 665 - 674
  • [37] Space-Efficient Algorithms for Longest Increasing Subsequence
    Kiyomi, Masashi
    Ono, Hirotaka
    Otachi, Yota
    Schweitzer, Pascal
    Tarui, Jun
    35TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2018), 2018, 96
  • [38] Space-Efficient Algorithms for Longest Increasing Subsequence
    Masashi Kiyomi
    Hirotaka Ono
    Yota Otachi
    Pascal Schweitzer
    Jun Tarui
    Theory of Computing Systems, 2020, 64 : 522 - 541
  • [39] A fast algorithm for computing a longest common increasing subsequence
    Yang, IH
    Huang, CP
    Chao, KM
    INFORMATION PROCESSING LETTERS, 2005, 93 (05) : 249 - 253
  • [40] On the distribution of the length of the longest increasing subsequence of random permutations
    Baik, J
    Deift, P
    Johansson, K
    JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 1999, 12 (04) : 1119 - 1178
12345