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 条
  • [41] An algorithm for solving the longest increasing circular subsequence problem
    Deorowicz, Sebastian
    INFORMATION PROCESSING LETTERS, 2009, 109 (12) : 630 - 634
  • [42] The Length of the Longest Increasing Subsequence of a Random Mallows Permutation
    Carl Mueller
    Shannon Starr
    Journal of Theoretical Probability, 2013, 26 : 514 - 540
  • [43] Estimating the Longest Increasing Subsequence in Nearly Optimal Time
    Andoni, Alexandr
    Nosatzki, Negev Shekel
    Sinha, Sandip
    Stein, Clifford
    2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2022, : 708 - 719
  • [44] Efficient algorithms for finding a longest common increasing subsequence
    Wun-Tat Chan
    Yong Zhang
    Stanley P. Y. Fung
    Deshi Ye
    Hong Zhu
    Journal of Combinatorial Optimization, 2007, 13 : 277 - 288
  • [45] Longest Increasing Subsequence under Persistent Comparison Errors
    Barbara Geissmann
    Theory of Computing Systems, 2020, 64 : 662 - 680
  • [46] Computing the longest common almost-increasing subsequence
    Bhuiyan, Mohammad Tawhidul Hasan
    Alam, Muhammad Rashed
    Rahman, M. Sohel
    THEORETICAL COMPUTER SCIENCE, 2022, 930 : 157 - 178
  • [47] The longest almost increasing subsequence problem with sliding windows
    Ho, Cheng-Han
    Yang, Chang-Biau
    THEORETICAL COMPUTER SCIENCE, 2024, 1005
  • [48] On the Distribution of the Length of the Longest Increasing Subsequence in a Random Permutation
    James C. Fu
    Yu-Fei Hsieh
    Methodology and Computing in Applied Probability, 2015, 17 : 489 - 496
  • [49] A CGM algorithm solving the longest increasing subsequence problem
    Seme, David
    COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2006, PT 5, 2006, 3984 : 10 - 21
  • [50] On the Distribution of the Length of the Longest Increasing Subsequence in a Random Permutation
    Fu, James C.
    Hsieh, Yu-Fei
    METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY, 2015, 17 (02) : 489 - 496
12345