Sorting and Selection with Random Costs

DOI10.1007/978-3-540-78773-0_5zbMATH Open1136.68362arXiv0710.0083OpenAlexW1493342333MaRDI QIDQ5458516FDOQ5458516

Keshav Kunal, Stanislav Angelov, Andrew McGregor

Publication date: 15 April 2008

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

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.

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

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

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

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

Cited In (10)

• Efficient Sorting in a Dynamic Adverse-Selection Model
• Query-Competitive Sorting with Uncertainty.
• Moves and displacements of particular elements in quicksort
• Title not available (Why is that?)
• Searching for quicksand ideals in partially ordered sets
• Interchange rearrangement: the element-cost model
• On the cost of algorithms for random selection
• Sorting with expensive comparands
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Computing similarity distances between rankings

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)