2007/09/29 by Stanislav Angelov, Angelov, Stanislav, Keshav Kunal +3
Computer Science · Mathematics · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #cs.DS
paper · pdf · doi:10.48550/arxiv.0710.0083
arxiv created 2007/09/29 · openalex publication_date 2007/09/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
There is a growing body of work on sorting and selection in models other than the unit-cost comparison model. This work is the first treatment of 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.