Sorting and Selection with Random Costs
Sorting and Selection with Random Costs
复制标题
具有随机成本的排序和选择
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
A. Mcgregor
中科院分区：
文献类型：
--
作者：
Stanislav Angelov;K. Kunal;A. Mcgregor
除了单位成本比较模型之外，越来越多的工作是在模型中进行排序和选择。这项工作处理了问题的一个自然随机变量，其中比较两个元素的成本是一个随机变量。每个成本都是独立选择的，并且算法已知。特别地，我们考虑以下三个模型：每个费用在[0，1]范围内均匀选择，每个费用为0，概率为p，否则为1；或者，每个费用为1，概率为p，否则为无穷大。我们给出了这些问题的上下界(在大多数情况下是最优的)。我们通过精心设计算法来确保各个阶段产生的费用是独立的，并在适当的时候利用随机偏序的性质来获得我们的上界。
There is a growing body of work on sorting and selection in models other than the unit-cost comparison model. This work treats a natural stochastic variant of the problem where the cost of comparing two elements is a random variable. Each cost is chosen independently and is known to the algorithm. In particular we consider the following three models: each cost is chosen uniformly in the range [0, 1], each cost is 0 with some probability p and 1 otherwise, or each cost is 1 with probability p and infinite otherwise. We present lower and upper bounds (optimal in most cases) for these problems. We obtain our upper bounds by carefully designing algorithms to ensure that the costs incurred at various stages are independent and using properties of random partial orders when appropriate.