Comparison-based time-space lower bounds for selection

DOI10.1145/1721837.1721842MaRDI QIDQ2930302zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1721837.1721842

zbMATH Keywords

adversary argumentslower boundsmedian findingRAMrandomized algorithmsstreaming algorithmstime-space trade-offs

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Comparison-based time-space lower bounds for selection
• scientific article; zbMATH DE number 1383709
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
• Finding the Median (Obliviously) with Bounded Space

Cited in

(27)

• Upper bounds for time-space trade-offs in sorting and selection
• Constant work-space algorithms for facility location problems
• A time-space trade-off for computing the k-visibility region of a point in a polygon
• Finding median in read-only memory on integer input
• Computing the Burrows-Wheeler transform in place and in small space
• Memory-constrained algorithms for simple polygons
• Computing (and Life) Is All about Tradeoffs
• Time-space trade-off for finding the k-visibility region of a point in a polygon
• Finding the Median (Obliviously) with Bounded Space
• Reprint of: Memory-constrained algorithms for simple polygons
• Computing a visibility polygon using few variables
• Comparison-based time-space lower bounds for selection
• Artificial Intelligence and Soft Computing - ICAISC 2004
• scientific article; zbMATH DE number 1383709 (Why is no real title available?)
• Priority queues and sorting for read-only data
• Space-time trade-offs for stack-based algorithms
• Finding the minimum number of elements with sum above a threshold
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• scientific article; zbMATH DE number 7250167 (Why is no real title available?)
• The shifting sands algorithm
• Sorting and ranking of self-delimiting numbers with applications to tree isomorphism
• Linear-time in-place selection in less than 3n comparisons
• Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs
• Sorting and ranking of self-delimiting numbers with applications to outerplanar graph isomorphism
• Selection from read-only memory with limited workspace
• Strictly in-place algorithms for permuting and inverting permutations
• Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)

This page was built for publication: Comparison-based time-space lower bounds for selection

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