Sorting and Selection with Random Costs

DOI10.1007/978-3-540-78773-0_5zbMath1136.68362arXiv0710.0083OpenAlexW1493342333MaRDI QIDQ5458516

Keshav Kunal, Stanislav Angelov, 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)

Related Items

Searching for quicksand ideals in partially ordered sets, Computing similarity distances between rankings, Interchange rearrangement: the element-cost model, Moves and displacements of particular elements in quicksort

Cites Work

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