Sorting and Selection with Random Costs

DOI10.1007/978-3-540-78773-0_5MaRDI QIDQ5458516zbMATH OpenOpenAlexFDO

Authors Stanislav Angelov, Keshav Kunal, Andrew McGregor

Publication date 15 April 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0710.0083

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 2079316
• Randomized selection in \(n+C+o(n)\) comparisons
• Probabilistic Parallel Algorithms for Sorting and Selection
• Sorting with expensive comparands
• scientific article; zbMATH DE number 4110087

Cites work

• A new strategy for querying priced information
• Algorithms – ESA 2005
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Balancing poset extensions
• Entropy and sorting.
• Finite partially ordered sets and their corresponding permutation sets
• How good is the information theory bound in sorting?
• scientific article; zbMATH DE number 1003302 (Why is no real title available?)
• scientific article; zbMATH DE number 446489 (Why is no real title available?)
• scientific article; zbMATH DE number 2079316 (Why is no real title available?)
• Linear extensions of a random partial order
• Matching Nuts and Bolts in O(n log n) Time
• On the value of a random minimum spanning tree problem
• Query strategies for priced information
• Sorting and selection in posets
• The Information-Theoretic Bound is Good for Merging

Cited in

(13)

• Moves and displacements of particular elements in quicksort
• Computing similarity distances between rankings
• Sorting with expensive comparands
• Sorting and selection with equality comparisons
• On the cost of algorithms for random selection
• scientific article; zbMATH DE number 2079316 (Why is no real title available?)
• Searching for quicksand ideals in partially ordered sets
• Query-Competitive Sorting with Uncertainty.
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Efficient Sorting in a Dynamic Adverse-Selection Model
• Energy efficient sorting, selection and searching
• Algorithms for the generalized poset sorting problem
• Interchange rearrangement: the element-cost model

This page was built for publication: Sorting and Selection with Random Costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458516)